模板

FFT

见miskcoo博客

FFT

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
namespace Fast_Fourier_Transform{
    const int MAXN = 300000+9;
    const double PI = acos(-1.0);
    int size,bit_length;
    int loc[MAXN];
    struct C{
        double x,y;
        C(double _x=0,double _y=0):x(_x),y(_y){}
    };
    C operator + (const C &A,const C &B){
        return C(A.x+B.x,A.y+B.y);
    }
    C operator - (const C &A,const C &B){
        return C(A.x-B.x,A.y-B.y);
    }
    C operator * (const C &A,const C &B){
        return C(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
    }
    C A1[MAXN],B1[MAXN];
    void INIT(int len){
        for(size=1,bit_length=-1;size<len;size<<=1,bit_length++);
        int now=0;
        for(int i=0;i<size;i++){
            loc[i]=now;
            for(int j=1<<bit_length;(now^=j)<j;j>>=1);
        }
    }
    void DFT(int *A,C *re){
        for(int i=0;i<size;i++)
            re[i].x=A[loc[i]];
        for(int k=2;k<=size;k<<=1){
            int len=k>>1;
            C Wn(cos(2.0*PI/(1.0*k)),sin(2.0*PI/(1.0*k)));
            for(int i=0;i<size;i+=k){
                C W(1,0);
                for(int j=0;j<len;j++,W=W*Wn){
                    C u=re[i+j],v=W*re[i+j+len];
                    re[i+j]=u+v;
                    re[i+j+len]=u-v;
                }
            }
        }
    }
    void IDFT(C *A,C *re){
        for(int i=0;i<size;i++)
            re[i]=A[loc[i]];
        for(int k=2;k<=size;k<<=1){
            int len=k>>1;
            C Wn(cos(-2.0*PI/(1.0*k)),sin(-2.0*PI/(1.0*k)));
            for(int i=0;i<size;i+=k){
                C W(1,0);
                for(int j=0;j<len;j++,W=W*Wn){
                    C u=re[i+j],v=W*re[i+j+len];
                    re[i+j]=u+v;
                    re[i+j+len]=u-v;
                }
            }
        }
        for(int i=0;i<size;i++)
            re[i].x/=1.0*size;
    }
    void FFT(int *A,int *B,int *ans){
        DFT(A,A1);DFT(B,B1);
        for(int i=0;i<size;i++)
            A1[i]=A1[i]*B1[i];
        IDFT(A1,B1);
        for(int i=0;i<size;i++)
            ans[i]=(int)(B1[i].x+0.5);
    }
}
using namespace Fast_Fourier_Transform;
int num1[MAXN],num2[MAXN];
int ANS[MAXN];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    INIT(n+m+3);
    for(int i=0;i<=n;i++)
        scanf("%d",&num1[i]);
    for(int i=0;i<=m;i++)
        scanf("%d",&num2[i]);
    FFT(num1,num2,ANS);
    for(int i=0;i<=m+n;i++)
        printf("%d ",ANS[i]);
    puts("");
    return 0;
}

NTT

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 300000;
class Fast_Number_Theory_Transform{
    private:
        const int MOD,G;
        int size,bit_length;
        int loc[MAXN];
        int A1[MAXN],B1[MAXN];
        int qpow(int x,int k){
            int mul=x;
            int re=1;
            for(int i=1;i<=k;i<<=1){
                if(i&k)
                    re=1LL*re*mul%MOD;
                mul=1LL*mul*mul%MOD;
            }
            return re;
        }
        int inv(int x){
            return qpow(x,MOD-2);
        }
        void DFT(int *A,int *re){
            for(int i=0;i<size;i++)
                re[i]=A[loc[i]];
            for(int k=2;k<=size;k<<=1){
                int len=k>>1;
                int Wn=qpow(G,(MOD-1)/k);
                for(int i=0;i<size;i+=k){
                    int W=1;
                    for(int j=0;j<len;j++){
                        int u=re[i+j],v=1LL*re[i+j+len]*W%MOD;
                        re[i+j]=(u+v)%MOD;
                        re[i+j+len]=(u-v+MOD)%MOD;
                        W=1LL*W*Wn%MOD;
                    }
                }
            }
        }
        void IDFT(int *A,int *re){
            for(int i=0;i<size;i++)
                re[i]=A[loc[i]];
            for(int k=2;k<=size;k<<=1){
                int len=k>>1;
                int Wn=inv(qpow(G,(MOD-1)/k));
                for(int i=0;i<size;i+=k){
                    int W=1;
                    for(int j=0;j<len;j++){
                        int u=re[i+j],v=1LL*re[i+j+len]*W%MOD;
                        re[i+j]=(u+v)%MOD;
                        re[i+j+len]=(u-v+MOD)%MOD;
                        W=1LL*W*Wn%MOD;
                    }
                }
            }
            int tmp=inv(size);
            for(int i=0;i<size;i++)
                re[i]=1LL*re[i]*tmp%MOD;
        }
    public:
        Fast_Number_Theory_Transform(int _x,int _y):MOD(_x),G(_y){}
        void Transform(int *A,int *B,int *ans){
            DFT(A,A1);DFT(B,B1);
            for(int i=0;i<size;i++)
                A1[i]=1LL*A1[i]*B1[i]%MOD;
            IDFT(A1,ans);
        }
        void init(int x){
            for(size=1,bit_length=-1;size<x;size<<=1,bit_length++);
            int now=0;
            for(int i=0;i<size;i++){
                loc[i]=now;
                for(int j=1<<bit_length;(now^=j)<j;j>>=1);
            }
        }
}NTT((479<<21)+1,3);
int a[MAXN],b[MAXN];
int ans[MAXN];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<=m;i++)
        scanf("%d",&b[i]);
    NTT.init(n+m+1);
    NTT.Transform(a,b,ans);
    for(int i=0;i<=m+n;i++)
        printf("%d ",ans[i]);
    puts("");
    return 0;
}