zcmimi's blog

NTT基本上跟FFT一样,就是把单位根换成了原根(原根和单位根一样具有FFT需要的特殊性质)

前置知识:

  1. FFT

  2. 原根

原根的性质

p是质数,g为模p的原根,n|(p-1),g_n=g^{(p-1)/n}

单位根:

\omega_n^n=1,\omega_n^{n/2}=-1

原根:

g_n^n=g^{p-1}\equiv 1\mod p

g_n^{n/2}=g^{(p-1)/2}

其中\left(g^{(p-1)/2}\right)^2=1,g_n^{n/2}=\pm1

由于g是原根,所以g^{p-1}\neq g^{(p-1)/2},所以g_n^{n/2}=-1

单位根:w_{dn}^{dk}=w_n^k

原根:

g_{dn}^{dk}=g^{dk(p-1)/(dn)}=g^{k(p-1)/n}=g_n^k

单位根: ({w_n^k})^2=w_{n/2}^k

原根:

(g_n^k)^2=g_n^{2k}=g_{n/2}^k

(g_n^{k+n/2})^2=g_n^{2k+n}\equiv g_n^{2k}=g_{n/2}^k

FFT需要单位复数根该有的性质原根都有

实现

和FFT基本上一样

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define For(i,x,y) for(int i=x;i<=y;++i)
#define il __inline__ __attribute__ ((always_inline))
il int gi(){char c;int x=0,f=0;while((c=getchar())<'0'||'9'<c)f^=(c=='-');while('0'<=c&&c<='9')x*=10,x+=c-48,c=getchar();return f?-x:x;}
const int N=3000011,P=998244353,G=3,Gi=332748118;
int n,m,limit=1,l=0,r[N],a[N],b[N];
il int pw(int x,int p){
    int ans=1;
    while(p){
        if(p&1)ans=1ll*ans*x%P;
        x=1ll*x*x%P;p>>=1;
    }
    return ans;
}
il void ntt(int *A,int typ){
    For(i,0,limit-1)
        if(i<r[i])std::swap(A[i],A[r[i]]);
    for(int len=1;len<limit;len<<=1){
        int Wn=pw(~typ?G:Gi,(P-1)/(len<<1));
        //Gi指1/G在模P下的逆元,相当于pw(G,P-2)
        for(int i=0;i<limit;i+=(len<<1)){
            int w=1;
            For(k,0,len-1){//蝴蝶操作
                int t=1ll*w*A[i+k+len]%P;
                A[i+k+len]=(A[i+k]-t+P)%P;
                A[i+k]=(A[i+k]+t)%P;
                w=1ll*w*Wn%P;
            }
        }
    }
}
int main(){
    n=gi(),m=gi();
    For(i,0,n)a[i]=(gi()+P)%P;
    For(i,0,m)b[i]=(gi()+P)%P;
    while(limit<=n+m)limit<<=1,++l;
    For(i,0,limit-1)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    ntt(a,1);ntt(b,1);
    For(i,0,limit)a[i]=1ll*a[i]*b[i]%P;
    ntt(a,-1);
    int inv=pw(limit,P-2);//limit在模P下的逆元
    For(i,0,n+m)printf("%d ",1ll*a[i]*inv%P);
}

常用模数与原根

模数 原根 备注
998244353 3 2^{23}\times 7\times 17+1
469762049 3 7\times 2^{26}+1
1004535809 3 479\times 2^{21}+1
快速数论变换 ntt
comment评论
Search
search