3992: [SDOI2015]序列统计
Submit: 1681 Solved: 780
[Submit][Status][Discuss]
Description
小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
Input
一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。第二行，|S|个整数，表示集合S中的所有元素。
Output
一行，一个整数，表示你求出的种类数mod 1004535809的值。
Sample Input
4 3 1 2
1 2
1 2
Sample Output
8
HINT
【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。
【数据规模和约定】
对于10%的数据，1<=N<=1000；
对于30%的数据，3<=M<=100；
对于60%的数据，3<=M<=800；
对于全部的数据，1<=N<=109，3<=M<=8000，M为质数，1<=x<=M-1，输入数据保证集合S中元素不重复
Source
先随便找出M的一个原根 （原根很多，对于一个模数M原根大致有phi(phi(M))个），然后把S集合中的数都转化成指标。
(顺便科普一下如何判断一个数是不是原根，因为原根要遍历1-M-1的同余系下的所有元素，所以原根在M-1次方之前
是不能等于1的。然而不用一个次方一个判断，直接判断在M-1的约数除是否有1就行了(其实还可以更优化，即只判断/某个质因子之后的约数
就行了，但是这个方法本题已经够用了))
这样之后mod M同余系下两个数相乘就相当于它们的指标相加。
你问我这个有什么用？？
转化成加法之后就可以卷积了啊，不转化的话只能Ｏ(Ｎ^２)算。
然后这里有一个超级超级超级超级超级超级大的大坑是集合Ｓ中的元素是非负整数！！！
不是正整数是非负整数！！！
如果有一个元素是０的话那它是没有意义的(0没有指标啊，然而一开始没有特判让idx==0的强行加了1hhhh)
转化之后构造一个关于指标的元多项式，它的N次方的idx[x]次项的系数就是答案。
可以用求快速幂类似的方法倍增求解，不过每一次乘完了之后要维护一下次数>=M-1的(因为指标的值都是<=M-2的)，
把它们的值加到 mod(M-1)同余系下的<M-1的次数项上 (如果你问为什么不是 mod M同余系下那么我建议你去学一下欧拉定理)
然后几乎就是个NTT的板了。
/************************************************************** Problem: 3992 User: JYYHH Language: C++ Result: Accepted Time:4656 ms Memory:2116 kb ****************************************************************/ #include<bits/stdc++.h> #define ll long long #define mod 1004535809 #define maxn 30005 using namespace std; const int pi=3,ni=mod/pi+1; int di[maxn],tot,N,M,X,num,inv; int a[maxn],p,b[maxn],ind[maxn]; int r[maxn],e[maxn],l,n,ans[maxn]; inline int add(int x,int y,const int ha){ x+=y; if(x>=ha) x-=ha; return x; } inline int dec(int x,int y,const int ha){ x-=y; if(x<0) x+=ha; return x; } inline int mul(int x,int y,const int ha){ return (ll)x*y%ha; } inline int ksm(int x,int y,int ha){ int an=1; for(;y;y>>=1,x=(ll)x*x%ha) if(y&1) an=(ll)an*x%ha; return an; } inline bool can(int x){ for(int i=1;i<=tot;i++) if(ksm(x,di[i],M)==1) return 0; return 1; } inline void get(){ for(int i=2;i<M;i++) if(can(i)){ p=i; break; } } inline void prework(){ ind[1]=0; for(int i=1,j=p;j!=1;i++,j=(ll)j*p%M){ ind[j]=i; } } inline void NTT(int *c,int f){ for(int i=0;i<n;i++) if(i<r[i]) swap(c[i],c[r[i]]); for(int i=1;i<n;i<<=1){ int omega=(f==1?ksm(pi,(mod-1)/(i<<1),mod):ksm(ni,(mod-1)/(i<<1),mod)); for(int j=0,q=i<<1;j<n;j+=q){ int now=1; for(int k=0;k<i;k++,now=mul(now,omega,mod)){ int x=c[k+j],y=mul(now,c[k+j+i],mod); c[k+j]=add(x,y,mod); c[k+j+i]=dec(x,y,mod); } } } if(f!=1) for(int i=0;i<n;i++) c[i]=mul(c[i],inv,mod); } inline void calc(int *x,int *y){ NTT(x,1),NTT(y,1); for(int i=0;i<n;i++) x[i]=mul(x[i],y[i],mod); NTT(x,-1); int D=M-1,to; for(int i=0;i<D;i++){ to=i+D; x[i]=add(x[i],x[to],mod); } for(int i=D;i<n;i++) x[i]=0; } inline void solve(){ for(n=1,l=0;n<=((M-2)<<1);n<<=1) l++; for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); inv=ksm(n,mod-2,mod); ans[0]=1; while(N){ if(N&1){ for(int i=0;i<n;i++) e[i]=b[i]; calc(ans,e); } for(int i=0;i<n;i++) e[i]=b[i]; calc(b,e); N>>=1; } } int main(){ scanf("%d%d%d%d",&N,&M,&X,&num); M--; for(int i=2;i*i<=M;i++) if(!(M%i)){ di[++tot]=i; if(i*i!=M) di[++tot]=M/i; } M++; for(int i=1;i<=num;i++) scanf("%d",a+i); get(); prework(); for(int i=1;i<=num;i++) if(a[i]) b[ind[a[i]]]=1; solve(); printf("%d ",ans[ind[X]]); return 0; }