FFT模板

typedef cp complex<double>
void FFT(cp *a,int n,int op){//同上
    if(!n)return;
    cp a0[n],a1[n];
    for(int i=0;i<n;++i)
        a0[i]=a[i<<1],a1[i]=a[i<<1|1];
    FFT(a0,n>>1,op);FFT(a1,n>>1,op);
    cp W(cos(PI/n),sin(PI/n)*op),w(1,0);
    for(int i=0;i<n;++i,w*=W)
        a[i]=a0[i]+w*a1[i],a[i+n]=a0[i]-w*a1[i];
}
cp f[N],g[N];
void solve(){
    int n,m;
    n=read();m=read();
    for(int i=0;i<=n;++i)f[i]=read();
    for(int i=0;i<=m;++i)g[i]=read();
    for(m+=n,n=1;n<=m;n<<=1);//把长度补到2的幂，不必担心高次项的系数，因为默认为0
    FFT(f,n>>1,1);FFT(g,n>>1,1);//DFT
    for(int i=0;i<n;++i)f[i]*=g[i];//点值直接乘
    FFT(f,n>>1,-1);//IDFT
    for(int i=0;i<=m;++i)printf("%.0f ",fabs(f[i].real())/n);//注意结果除以n，小心“-0”
    puts("");
}