首先类似实数域的对数，我们在模意义下有离散对数ind。设模数为m，m的原根为g，则ind(i)=j表明gj≡imodm。根据原根的性质，我们知道{ind(x)}和{x}是一一对应的。
类似对数，我们可以把模意义下的乘法运算化作模意义下的加法运算：
ind(xy%m)=(ind(x)+ind(y))%m−1
因此我们就是要求n个数的和为ind[x]的有多少种。
我们可以写出生成函数f(x)，那么fn(x)中xind[X]的系数就是答案。
多项式快速幂+ntt加速多项式乘法即可。
复杂度O(mlogmlogn) #include #include #include #include using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 8010 #define G 3 #define mod 1004535809 inline char gc(){ static char buf[1<<16],*S,*T; if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(S==T) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f; } int nn,mm,n,m,X,L=0,R[N<<2],inv,ind[N]; inline int ksm(int x,int k,int mo){ int res=1;for(;k;k>>=1,x=(ll)x*x%mo) if(k&1) res=(ll)res*x%mo;return res; } inline void ntt(int *a,int f){ for(int i=0;iif(ifor(int i=1;iint wn=ksm(G,f==1?(mod-1)/(i<<1):mod-1-(mod-1)/(i<<1),mod); for(int j=0,p=i<<1;jint w=1; for(int k=0;kint x=a[j+k],y=(ll)w*a[j+k+i]%mod; a[j+k]=(x+y)%mod;a[j+k+i]=(x-y)%mod; } } }if(f==-1) for(int i=0;istruct Poly{ int a[N<<2]; Poly(){} Poly(bool t){memset(a,0,sizeof(a));if(t) a[0]=1;} friend Poly operator*(Poly a,Poly b){ ntt(a.a,1);ntt(b.a,1); for(int i=0;i1); for(int i=mm;i0; return a; } friend Poly operator^(Poly a,int k){ Poly res(1);for(;k;k>>=1,a=a*a) if(k&1) res=res*a;return res; } }a; inline int getrt(){ int i; for(i=2;i;++i){ bool pd=1; for(int j=2;j*j<=mm-1;++j) if((mm-1)%j==0&&ksm(i,(mm-1)/j,mm)==1){pd=0;break;} if(pd) return i; } } int main(){ // freopen("a.in","r",stdin); nn=read();mm=read();X=read(); int g=getrt(); for(int i=0,x=1;i1;x=(x*g)%mm,++i) ind[x]=i;mm--; m=mm<<1;for(n=1;n<=m;n+=n) ++L;inv=ksm(n,mod-2,mod); for(int i=0;i>1]>>1)|(i&1)<1; int owo=read(); while(owo--){int x=read();if(x) a.a[ind[x]]=1;} a=a^nn;int ans=a.a[ind[X]];if(ans<0) ans+=mod; printf("%d ",ans); return 0; }