【BZOJ3992】【SDOI2015】序列统计 EGF+多项式快速幂+循环卷积
如果是求$n$个数之和在模$m$意义下为$x$，那么做法是显然的。
但是这道题问的是$n$个数之积在模m意义下为$x$，那么做法就和上面的问题不同。
考虑如何把乘法转换成加法（求log）：
题目中有一个很特殊的条件：$m$是个质数。
不妨假设$m$的原根为$g$。那么显然，我们可以用$g^x%m$构造出$[0,m)$中的所有数。
那么对于两个数$A$和$B$，我们将它变形为$g^{x_1}$和$g^{x_2}$，那么$A \times B=g^{x_1+x_2}$。
我们构造一个m-1次多项式A，对于A的第i项，A_i=$\begin{equation} \left\{ \begin{array}{lr} 1 \ [x^i \equiv k(mod\ m),\ k∈S].\\0 \end{array} \right. \end{equation}$。
然后，不妨设读入的$X=g^k$，则答案即为$[x^k]A^n(x)$，注意这里的卷积是循环卷积。
然后就没了，注意S中出现0的情况。
1 #include<bits/stdc++.h>
2 #define M 32768
3 #define MOD 1004535809
4 #define G 3
5 #define L long long
6 using namespace std;
7
8 L pow_mod(L x,L k){
9 L ans=1;
10 while(k){
11 if(k&1) ans=ans*x%MOD;
12 x=x*x%MOD; k>>=1;
13 }
14 return ans;
15 }
16
17 void change(L a[],int n){
18 for(int i=0,j=0;i<n-1;i++){
19 if(i<j) swap(a[i],a[j]);
20 int k=n>>1;
21 while(j>=k) j-=k,k>>=1;
22 j+=k;
23 }
24 }
25 void NTT(L a[],int n,int on){
26 change(a,n);
27 for(int h=2;h<=n;h<<=1){
28 L wn=pow_mod(G,(MOD-1)/h);
29 for(int j=0;j<n;j+=h){
30 L w=1;
31 for(int k=j;k<j+(h>>1);k++){
32 L u=a[k],t=a[k+(h>>1)]*w%MOD;
33 a[k]=(u+t)%MOD;
34 a[k+(h>>1)]=(u-t+MOD)%MOD;
35 w=w*wn%MOD;
36 }
37 }
38 }
39 if(on==-1){
40 L inv=pow_mod(n,MOD-2);
41 for(int i=0;i<n;i++) a[i]=a[i]*inv%MOD;
42 reverse(a+1,a+n);
43 }
44 }
45 L a[M]={0},b[M]={0},ans[M]={0};
46 int gn[M]={0},g=0,vis[M]={0};
47
48 void get(int n){
49 for(int i=2;i<n;i++){
50 memset(vis,0,n<<2);
51 vis[0]=1; gn[1]=0;
52 int hh=1,ok=1;
53 for(int j=1;j<n-1;j++){
54 hh=hh*i%n;
55 if(vis[hh]){ok=0; break;}
56 vis[hh]=1; gn[hh]=j;
57 }
58 if(ok){g=i; return;}
59 }
60 }
61
62 int main(){
63 int n,m,x,s,nn=1;
64 scanf("%d%d%d%d",&n,&m,&x,&s);
65 while(nn<(m*2)) nn<<=1;
66 get(m);
67 for(int i=0;i<s;i++){
68 int x; scanf("%d",&x);
69 if(x==0) continue;
70 x=gn[x];
71 a[x]++;
72 }
73 ans[0]=1; m--;
74 while(n){
75 if(n&1){
76 NTT(a,nn,1); NTT(ans,nn,1);
77 for(int i=0;i<nn;i++) ans[i]=ans[i]*a[i]%MOD;
78 NTT(a,nn,-1); NTT(ans,nn,-1);
79 for(int i=0;i<m;i++) ans[i]=(ans[i]+ans[i+m])%MOD;
80 for(int i=m;i<nn;i++) ans[i]=0;
81 }
82 NTT(a,nn,1);
83 for(int i=0;i<nn;i++) a[i]=a[i]*a[i]%MOD;
84 NTT(a,nn,-1);
85 for(int i=0;i<m;i++) a[i]=(a[i]+a[m+i])%MOD;
86 for(int i=m;i<nn;i++) a[i]=0;
87 n>>=1;
88 }
89 printf("%lld\n",ans[gn[x]]);
90 }