三模数NTT模板

求两个多项式的卷积对任意数p取模

两个好记的FNT模数：

5*2^25+1

7*2^26+1

原根都为3

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=,g=;

 typedef long long LL;

 typedef double db;

 typedef long double LD;

 using namespace std;

 int n,m,mod;

 LL a[][N],b[][N],p[]={,,},gi[]={,,};

 LL ans[N];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 LL ksc(LL a,LL b,LL p) {

     LL tp=a*b-(LL)((LD)a/p*b+1.0e-8)*p;

     return tp<?tp+p:tp%p;

 }

 LL ksm(LL a,LL b,LL p) {

     LL rs=,bs=a%p;

     while(b) {

         if(b&) rs=ksc(rs,bs,p);

         bs=ksc(bs,bs,p);

         b>>=;

     }

     return rs;

 }

 int l,rev[N];

 void FFT(int n,LL a[],int f,int p,int gi) {

     For(i,,n-) if(i<rev[i]) swap(a[i],a[rev[i]]);

     for(int i=;i<n;i<<=) {

         LL wi=ksm((f==)?g:gi,(p-)/(i<<),p);

         for(int j=,pp=(i<<);j<n;j+=pp) {

             LL w=;

             for(int k=;k<i;k++,w=w*wi%p) {

                 LL x=a[j+k],y=w*a[j+k+i]%p;

                 a[j+k]=(x+y)%p; a[j+k+i]=(x-y+p)%p;

             }

         }

     }

     if(f==-) {

         LL inv=ksm(n,p-,p);

         For(i,,n) a[i]=a[i]*inv%p;

     }

 }

 int main() {

 #ifdef ANS

     freopen(".in","r",stdin);

     freopen(".out","w",stdout);

 #endif

     read(n); read(m); read(mod);

     For(i,,n) { read(a[][i]); a[][i]=a[][i]=a[][i]; }

     For(i,,m) { read(b[][i]); b[][i]=b[][i]=b[][i]; }

     m+=n;

     for(n=;n<=m;n<<=) l++;

     For(i,,n) rev[i]=(rev[i>>]>>)|((i&)<<(l-));

     For(i,,) {

         FFT(n,a[i],,p[i],gi[i]);

         FFT(n,b[i],,p[i],gi[i]);

         For(j,,n) a[i][j]=a[i][j]*b[i][j]%p[i];

         FFT(n,a[i],-,p[i],gi[i]);

     }

     LL p1=p[],p2=p[],p3=p[];

     For(i,,m) {

         LL b1=a[][i],b2=a[][i],b3=a[][i],b4;

         b4=(ksc(ksc(b1,ksm(p2,p1-,p1),p1*p2),p2,p1*p2)+ksc(ksc(b2,ksm(p1,p2-,p2),p1*p2),p1,p1*p2))%(p1*p2);

         LL k=((b3%p3-b4%p3+p3)%p3)*ksm(p1*p2,p3-,p3)%p3;

         ans[i]=(b4%mod+k*p1%mod*p2%mod)%mod;

     }

     For(i,,m) printf("%lld ",ans[i]); puts("");

     Formylove;

 }