我终于会写FFT啦!!!

NTT和FFT常数及空间对比
上面是FFT,下面是NTT.


FFT板子

#include<cmath>
#include<cstdio>
#include<algorithm>
#define N (1<<21)+10
#define DFT 1
#define IDFT -1
using namespace std;
const double pi=acos(-1);
int n;
char a[60060],b[60060];
struct comp{
    double x,y;
    comp(double a=0,double b=0){x=a,y=b;}
    friend comp operator +(const comp &a,const comp &b){return comp(a.x+b.x,a.y+b.y);}
    friend comp operator -(const comp &a,const comp &b){return comp(a.x-b.x,a.y-b.y);}
    friend comp operator *(const comp &a,const comp &b){return comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
}A[N],B[N];
int limit=1,length,pos[N],ans[N];
void FFT(comp A[],int type){
    for(int i=0;i<limit;i++)
        if(i<pos[i])swap(A[i],A[pos[i]]);
    for(int mid=1;mid<limit;mid<<=1){
        comp w(cos(pi/mid),type*sin(pi/mid));
        for(int len=mid<<1,l=0;l<limit;l+=len){
            comp x(1,0);
            for(int i=l;i<l+mid;i++,x=x*w){
                comp a=A[i],b=x*A[i+mid];
                A[i]=a+b,A[i+mid]=a-b;
            }
        }
    }
    if(type==IDFT)
        for(int i=0;i<limit;i++)
            A[i].x/=limit;
}
int main(){
    scanf("%d%s%s",&n,a+1,b+1);
    for(int i=0;i<n;++i)
        A[i].x=a[n-i]-'0',
        B[i].x=b[n-i]-'0';
    while(limit<=n+n)
        limit<<=1,++length;
    for(int i=0;i<limit;i++)
        pos[i]=pos[i>>1]>>1|(i&1)<<(length-1);
    FFT(A,DFT),FFT(B,DFT);
    for(int i=0;i<limit;i++)A[i]=A[i]*B[i];
    FFT(A,IDFT);
    for(int i=0;i<limit;i++){
        ans[i]+=int(A[i].x+0.5);
        if(ans[i]>10)
            ans[i+1]+=ans[i]/10,
            ans[i]%=10;
    }
    bool pr=false;
    for(int i=limit;i>=0;--i){
        if(ans[i])
            printf("%d",ans[i]),
            pr=true;
        else if(pr)
            printf("0");
    }
    putchar('\n');
}

NTT板子

#include<cmath>
#include<cstdio>
#include<algorithm>
#define N (1<<21)+10
#define DFT 0
#define IDFT 1
#define rei register int
using namespace std;
int pow(int,int);
const int mod=998244353,g=3,gi=pow(g,mod-2);
int n,A[N],B[N];
char a[60060],b[60060];
inline int pow(int x,int n){
    int ret=1;
    while(n){
        if(n&1)ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;
        n>>=1;
    }
    return ret;
}
int limit=1,length,pos[N];
inline void NTT(int A[],int type){
    for(rei i=0;i<limit;i++)
        if(i<pos[i])swap(A[i],A[pos[i]]);
    for(rei mid=1;mid<limit;mid<<=1){
        int w=pow(type?gi:g,(mod-1)/(mid<<1));
        for(rei len=mid<<1,l=0;l<limit;l+=len){
            int x=1;
            for(rei i=l;i<l+mid;i++,x=1ll*x*w%mod){
                int a=A[i],b=1ll*x*A[i+mid]%mod;
                A[i]=(a+b)%mod,A[i+mid]=(a-b)%mod;
            }
        }
    }
    int rev=pow(limit,mod-2);
    if(type)
        for(rei i=0;i<limit;i++)
            A[i]=1ll*A[i]*rev%mod;
}
int main(){
    scanf("%d%s%s",&n,a+1,b+1);
    for(rei i=0;i<n;++i)
        A[i]=a[n-i]-'0',
        B[i]=b[n-i]-'0';
    while(limit<=n+n)
        limit<<=1,++length;
    for(rei i=0;i<limit;i++)
        pos[i]=pos[i>>1]>>1|(i&1)<<(length-1);
    NTT(A,DFT),NTT(B,DFT);
    for(rei i=0;i<limit;i++)A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,IDFT);
    for(rei i=0;i<limit;i++){
        A[i]=(A[i]+mod)%mod;
        if(A[i]>10)
            A[i+1]+=A[i]/10,
            A[i]%=10;
    }
    bool pr=false;
    for(rei i=limit;i>=0;--i){
        if(A[i])
            printf("%d",A[i]),
            pr=true;
        else if(pr)
            printf("0");
    }
    putchar('\n');
}

血まみれからの方がさ,勝つ時にはカッコイイだろう.