。。恩 打了四五遍 不会也背出来了。。
BZOJ3160 【听说时限紧？转C++的优势么？】
上AC代码 fft
1 /*Problem: 3160 2 User: cyz666 3 Language: C++ 4 Result: Accepted 5 Time:1992 ms 6 Memory:18492 kb 7 ****************************************************************/ 8 9 #include <bits/stdc++.h> 10 #define LL long long 11 const LL mo=1000000007; 12 const double pi=acos(-1.0); 13 using namespace std; 14 struct cp{ 15 double x,y; 16 cp(double a=0,double b=0):x(a),y(b){} 17 //cp(double a=0,double b=0){x=a,y=b;} 18 }a[400005],b[400005],W[200005]; 19 int h[400005],rev[400005],f[200005],c[200005],n,x,m; 20 char s; LL ans; 21 cp operator +(cp a,cp b){ 22 cp c(a.x+b.x,a.y+b.y); 23 return c; 24 } 25 cp operator *(cp a,cp b){ 26 cp c(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); 27 return c; 28 } 29 cp operator -(cp a,cp b){ 30 return (cp){a.x-b.x,a.y-b.y}; 31 } 32 void fft(cp a[],int n,int d=1){ 33 if (d<0) reverse(a+1,a+n); 34 for (int i=0;i<n;++i) 35 if (i<rev[i]) swap(a[i],a[rev[i]]); 36 for (int i=0;i<n/2;++i) 37 W[i]=cp(cos(2*pi/n*i),sin(2*pi/n*i)); 38 for (int m=2,k=1;m<=n;k=m,m<<=1) 39 for (int i=0;i<n;i+=m) 40 for (int j=i;j<i+k;++j){ 41 cp u=a[j],v=a[j+k]*W[n/m*(j-i)]; 42 a[j]=u+v,a[j+k]=u-v; 43 } 44 if (d<0) for (int i=0;i<n;++i) a[i].x/=n; 45 } 46 int main(){ 47 while (scanf("%c",&s)&&isalpha(s)) 48 s=='a'?c[++++n]=1:c[++++n]=2; 49 c[0]=-1; c[n+2]=-2; 50 for (int i=1;i<=n;++i){ 51 if (x+f[x]>i) f[i]=min(f[x+x-i],x+f[x]-i); 52 while (c[i+f[i]]==c[i-f[i]]) ++f[i]; --f[i]; 53 if (i+f[i]>x+f[x]) x=i; 54 ans+=f[i]/2; if (ans>=mo) ans-=mo; 55 } 56 m=ceil((log(n)/log(2))); m=1<<m; 57 for (int i=1;i<m;++i)rev[i]=(rev[i>>1]>>1)+(m>>1)*(i&1); 58 x=0; for (int i=2;i<=n;++++i) c[++x]=c[i]; n=x; 59 for (int i=1;i<=n;++i) c[i]==1?a[i].x=1:b[i].x=1; 60 fft(a,m); fft(b,m); 61 for (int i=0;i<m;++i) a[i]=a[i]*a[i],b[i]=b[i]*b[i]; 62 fft(a,m,-1); fft(b,m,-1); 63 h[0]=1; for (int i=1;i<=n;++i)h[i]=(h[i-1]+h[i-1])%mo; 64 int x; ans=mo-ans; 65 for (int i=1;i<n+n;++i){ 66 x=round(a[i].x+b[i].x); 67 ans+=h[x+1>>1]-1; if (ans>=mo) ans-=mo; 68 } 69 ans=(ans-n+1+mo)%mo; 70 printf("%lld",ans); 71 return 0; 72 }
然后 顺手写了个ntt板子扔这（没用题目测过对不对）
mo的原根g的定义：g^1,g^2,...,g^(mo-1) 在%mo意义下各不相同。
1 #include <bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 int g1,g2,N,n,k,x,W[1050000],a[1050000],b[1050000],rev[1050000],mo1,mo2; 5 LL po(LL x,LL y,LL mo){ 6 LL z=1; if (y<0) y=y%(mo-1)+mo-1; 7 for (;y;y>>=1,x=x*x%mo) 8 if (y&1) z=z*x%mo; 9 return z; 10 } 11 int getg(LL mo){ 12 LL y=mo-1,x=floor(sqrt(y)); int fl; 13 for (int g=2;;++g){ 14 fl=1; 15 for (int i=2;i<=x;++i) if (!(y%i)) 16 if (po(g,i,mo)==1||po(g,y/i,mo)==1) {fl=0;break;} 17 if (fl) return g; 18 } 19 } 20 void ntt(int a[],int n,int d,int mo,int G){ //n整除(mo-1) 21 if (d<0) reverse(a+1,a+n); 22 for (int i=0;i<n;++i) 23 if (i<rev[i]) swap(a[i],a[rev[i]]); 24 W[0]=1; LL X=po(G,(mo-1)/n,mo); 25 for (int i=1;i<n/2;++i) W[i]=X*W[i-1]%mo; 26 for (int m=2,k=1;m<=n;k=m,m<<=1) 27 for (int i=0;i<n;i+=m) 28 for (int j=i;j<i+k;++j){ 29 int u=a[j],v=1ll*a[j+k]*W[n/m*(j-i)]%mo; 30 a[j]=u+v>=mo?u+v-mo:u+v; 31 a[j+k]=u-v<0?u-v+mo:u-v; 32 } 33 if (d<0){ 34 X=po(n,mo-2,mo); 35 for (int i=0;i<n;++i) a[i]=X*a[i]%mo; 36 } 37 } 38 int main(){ 39 mo1=998244353; mo2=1004535809; 40 g1=getg(mo1); g2=getg(mo2); 41 scanf("%d%d",&n,&k); W[0]=1; 42 for (int i=1;i<=n;++i) 43 scanf("%d",&x),a[x]=1,b[x]=1; 44 N=1048576; 45 for (int i=0;i<N;++i) rev[i]=rev[i>>1]>>1|(i&1?N>>1:0); 46 ntt(a,N,1,mo1,g1); ntt(b,N,1,mo2,g2); 47 for (int i=0;i<N;++i) 48 a[i]=po(a[i],k,mo1),b[i]=po(b[i],k,mo2); 49 ntt(a,N,-1,mo1,g1); ntt(b,N,-1,mo2,g2); 50 for (int i=0;i<N;++i){ 51 if (a[i]<0) a[i]+=mo1; 52 if (b[i]<0) b[i]+=mo2; 53 } 54 for (int i=0;i<N;++i) if (a[i]||b[i]) printf("%d ",i); puts(""); 55 return 0; 56 }
若多项式相乘的最高次为n， 则FFT,NTT的数组大小要开到>n的最小的2的幂。 即 1<<(int)ceil(log(n+1)/log(2))
给几个模数：
1004535809=479*2^21+1, 原根=3
998244353=7*17*2^23+1 ，原根=3
469762049=7*2^26+1 ，原根=3
