Luogu4245

只要做三次的NTT,快的飛起

普通NTT,做9次

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define debug(...) fprintf(stderr,__VA_ARGS__) #define Debug(x) cout<<#x<<"="<<x<<endl using namespace std; typedef long long LL; const int INF=1e9+7; inline LL read(){register LL x=0,f=1;register char c=getchar();while(c<48||c>57){if(c=='-')f=-1;c=getchar();}while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();return f*x; }namespace Math{inline int qpow(LL a,int b,int mod){LL res=1;while(b){if(b&1) (res*=a)%=mod;(a*=a)%=mod;b>>=1;}return (int)res;}inline int inv(int x,int mod){return qpow(x,mod-2,mod);} }using namespace Math;const int mod1=998244353,mod2=1004535809,mod3=469762049,G=3; const LL mod_1_2=(LL)mod1*mod2; const int inv_1=inv(mod1,mod2),inv_1_2=inv(mod_1_2%mod3,mod3); const int MAXN=3e5+5;int mod;struct Int{int A,B,C;inline Int(){}inline Int(int _num):A(_num),B(_num),C(_num){}inline Int(int _A,int _B,int _C):A(_A),B(_B),C(_C){}static inline Int add(Int x){///static不可省return Int(x.A+(x.A>>31&mod1),x.B+(x.B>>31&mod2),x.C+(x.C>>31&mod3));}inline friend Int operator + (Int x,Int y){return add(Int(x.A+y.A-mod1,x.B+y.B-mod2,x.C+y.C-mod3));}inline friend Int operator - (Int x,Int y){return add(Int(x.A-y.A,x.B-y.B,x.C-y.C));}inline friend Int operator * (Int x,Int y){return Int((LL)x.A*y.A%mod1,(LL)x.B*y.B%mod2,(LL)x.C*y.C%mod3);}inline int get(){LL x=(B-A+mod2)%mod2*inv_1%mod2*mod1+A;return ((C-x%mod3+mod3)%mod3*inv_1_2%mod3*(mod_1_2%mod)%mod+x)%mod;} }A[MAXN],B[MAXN];namespace N_T_T{Int Wn[MAXN],ilim;int rev[MAXN],limit=1,l;inline void init(int n){limit=1,l=0;while(limit<=n) limit<<=1,l++;for(int i=0;i<limit;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));Int w=(Int){qpow(G,(mod1-1)/limit,mod1),qpow(G,(mod2-1)/limit,mod2),qpow(G,(mod3-1)/limit,mod3)};Wn[0]=Int(1);for(int i=1;i<=limit;i++) Wn[i]=Wn[i-1]*w;//只有這里一個地方取=ilim=(Int){inv(limit,mod1),inv(limit,mod2),inv(limit,mod3)};}inline void NTT(Int *A,int type){for(int i=0;i<limit;i++)if(i<rev[i]) swap(A[i],A[rev[i]]);for(int len=1;len<limit;len<<=1){int t=(limit/len)>>1;for(int i=0;i<limit;i+=(len<<1))for(int j=0;j<len;j++){Int w=(type==1)?Wn[t*j]:Wn[limit-t*j];Int x=A[i+j],y=w*A[i+len+j];A[i+j]=x+y,A[i+len+j]=x-y;}}if(type==-1){for(int i=0;i<limit;i++) A[i]=A[i]*ilim;}} }using namespace N_T_T;int n,m;int main(){n=read(),m=read(),mod=read();for(int i=0;i<=n;i++) A[i]=Int(read()%mod);for(int i=0;i<=m;i++) B[i]=Int(read()%mod);init(n+m+2);NTT(A,1);NTT(B,1);for(int i=0;i<limit;i++) A[i]=A[i]*B[i];NTT(A,-1);//只要做三次for(int i=0;i<=n+m;i++)printf("%d ",A[i].get()); }

轉載于:https://www.cnblogs.com/lizehon/p/10501725.html

總結

以上是生活随笔為你收集整理的P4245 【模板】任意模数NTT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。