解法：
首先可以想到一个暴力dp，设f[i][j]表示选到第i个数，mod m=j的方案数。那么显然转移方程为f[i+1][j*k%m]+=f[i][j];
即f[i+1][j*k%m]=∑f[i][j]*num[k]（序列S中mod m=k的数的个数）
因为m是质数，所以m存在原根，我们可以通过离散对数的变换将乘法变为加法
原式变为f[i+1][(ind[j]+ind[k])%(m-1)]=∑f[i][ind[j]]*num[ind[k]]
为卷积形式，可使用FFT优化。
N很大，所以套一个快速幂即可
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; int n,m,x,L,i,k,N,ws,NN; int a[100011],pos[100011],b[100011],B[100011],d[100011]; int w[100011],ind[100011],h[100011]; int mo=1004535809; int mi(int x,int z) { int l; l=1; while(z){ if(z%2==1)l=(ll)l*x%mo; z/=2; x=(ll)x*x%mo; } return l; } bool isroot(int x) { int i,l; l=1; for(i=1;i<m-1;i++){ l=l*x%m; if(l==1)return false; } return true; } void prepare() { int i,j,k,g,l; //离散对数 for(i=1;i<m;i++)if(isroot(i)){ g=i; break; } l=1; for(i=1;i<m;i++){ l=l*g%m; ind[l]=i; } //fftN次单位复数根 N=1; while(N<2*m){ N*=2; ws++; } w[0]=1; w[1]=mi(3,(mo-1)/N); for(i=2;i<=N;i++)w[i]=(ll)w[i-1]*w[1]%mo; for(i=0;i<N;i++){ for(j=0;j<ws;j++){ k=(i&(1<<(ws-1-j))); if(k)pos[i]+=(1<<j); } } NN=mi(N,mo-2); } void Dft(int *a,int sig) { int i,half,u,v,j,l,wi; for(i=0;i<N;i++)h[pos[i]]=a[i]; for(l=1;l<=ws;l++){ half=1<<(l-1); for(i=0;i<half;i++){ wi=(sig>0)?w[i<<(ws-l)]:w[N-(i<<(ws-l))]; for(j=i;j<N;j+=(1<<l)){ u=h[j];v=(ll)h[j+half]*wi%mo; h[j]=(u+v)%mo; h[j+half]=((u-v)%mo+mo)%mo; } } } for(i=0;i<N;i++)a[i]=h[i]; } void fft(int *a,int *b) { int i; Dft(a,1); Dft(b,1); for(i=0;i<N;i++)a[i]=(ll)a[i]*b[i]%mo; Dft(a,-1); for(i=0;i<N;i++)a[i]=(ll)a[i]*NN%mo; for(i=m;i<N;i++){ a[(i%(m-1)==0)?(m-1):(i%(m-1))]=(a[(i%(m-1)==0)?(m-1):(i%(m-1))]+a[i])%mo; a[i]=0; } } void MT(int *b,int z) { int i; d[0]=1; while(z){ if(z%2==1){ for(i=0;i<N;i++)B[i]=b[i]; fft(d,b); for(i=0;i<N;i++)b[i]=B[i]; } z/=2; for(i=0;i<N;i++)B[i]=b[i]; fft(b,B); } } void Work() { a[ind[1]]++; MT(b,n); fft(a,d); printf("%d\n",a[ind[x]]); } int main() { scanf("%d%d%d%d",&n,&m,&x,&L); prepare(); for(i=1;i<=L;i++){ scanf("%d",&k); k%=m; b[ind[k]]++; } b[0]=0; Work(); }
原文：http://www.cnblogs.com/applejxt/p/4442601.html