数学（快速数论变换）：SDOI2015 序列统计

【题目描述】

小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。

小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

【输入格式】

一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。

第二行，|S|个整数，表示集合S中的所有元素。

【输出格式】

一行，一个整数，表示你求出的权值和mod 1004535809的值。

【样例输入】

4 3 1 2

1 2

【样例输出】

【提示】

对于10%的数据，1<=N<=1000；

对于30%的数据，3<=M<=100；

对于60%的数据，3<=M<=800；

对于全部的数据，1<=N<=10^9，3<=M<=8000，M为质数，0<=x<=M-1，输入数据保证集合S中元素不重复。

　　竟然没有x=0的数据。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 const int N=32768,G=3;
 6 const int MOD=1004535809;
 7 int g,n,m,x,s,pos[N],num[N];
 8 int Qpow(int x,int k,int mod){
 9     long long ret=1;
10     while(k){
11         if(k&1)ret=1ll*ret*x%mod;
12         x=1ll*x*x%mod;k>>=1;
13     }
14     return ret;
15 }
16 
17 void Rader(int *a,int len){
18     for(int i=1,j=len>>1;i<len-1;i++){
19         if(i<j)swap(a[i],a[j]);
20         int k=len>>1;
21         while(j>=k){
22             j-=k;
23             k>>=1;
24         }
25         j+=k;
26     }
27 }
28 
29 void NTT(int *a,int len,int on){
30     Rader(a,len);
31     for(int h=2,wn;h<=len;h<<=1){
32         if(on==1)wn=Qpow(G,(MOD-1)/h,MOD);
33         else wn=Qpow(G,MOD-1-(MOD-1)/h,MOD);
34         for(int j=0;j<len;j+=h){
35             int w=1,x,y;
36             for(int k=j;k<j+(h>>1);k++){
37                 x=a[k];y=1ll*a[k+(h>>1)]*w%MOD;
38                 a[k]=(x+y)%MOD;a[k+(h>>1)]=(x-y+MOD)%MOD;
39                 w=1ll*w*wn%MOD;
40             }
41         }
42     }
43     if(on==-1){
44         int inv=Qpow(len,MOD-2,MOD);
45         for(int i=0;i<len;i++)
46             a[i]=1ll*a[i]*inv%MOD;
47     }    
48 }
49 
50 int f[N],r[N],l=N/2;
51 void Solve(){
52     for(int i=0;i<N;i++)
53         r[i]=f[i];n-=1;
54     while(n){
55         NTT(f,N,1);
56         if(n&1){
57             NTT(r,N,1);
58             for(int i=0;i<N;i++)r[i]=1ll*r[i]*f[i]%MOD;
59             NTT(r,N,-1);
60             for(int i=m-1;i<N;i++)(r[i%(m-1)]+=r[i])%=MOD,r[i]=0;
61         }
62         for(int i=0;i<N;i++)f[i]=1ll*f[i]*f[i]%MOD;
63         NTT(f,N,-1);
64         for(int i=m-1;i<N;i++)(f[i%(m-1)]+=f[i])%=MOD,f[i]=0;
65         n>>=1;
66     }
67     printf("%d
",r[pos[x]]);
68 }
69 
70 void Solve_Zero(){int cnt=0,ans;
71     for(int i=1;i<=s;i++)if(!num[i])cnt++;
72     ans=Qpow(s,n,MOD)-Qpow(s-cnt,n,MOD);
73     printf("%d
",ans);
74 }
75 int main(){
76     freopen("sdoi2015_sequence.in","r",stdin);
77     freopen("sdoi2015_sequence.out","w",stdout);
78     scanf("%d%d%d%d",&n,&m,&x,&s);
79     for(int i=1;i<=s;i++)
80         scanf("%d",&num[i]);
81     if(!x)Solve_Zero();
82     for(g=1;g<m;g++){int i;
83         for(i=1;i<m-1;i++)
84             if(Qpow(g,i,m)==1)
85                 break;
86         if(i==m-1&&Qpow(g,m-1,m)==1)break;        
87     }
88     for(int i=1;i<m;i++)
89         pos[Qpow(g,i,m)]=i%(m-1);
90     for(int i=1;i<=s;i++)
91         if(num[i])f[pos[num[i]]]++;
92     Solve();
93     return 0;
94 }