模板 FFT 快速傅里叶变换

FFT模板，原理不难，优质讲解很多，但证明很难看太不懂

这模板题在bzoj竟然是土豪题，服了

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define dd double 
#define ll long long
#define N (1<<21)+10
using namespace std;

int n,m,ma;
int r[N];
dd const pi=acos(-1);
struct cp{
    dd x,y;
    cp(dd a,dd b):x(a),y(b){}
    cp(){}
    cp operator+(const cp &a){return cp(x+a.x,y+a.y);}
    cp operator-(const cp &a){return cp(x-a.x,y-a.y);}
    cp operator*(const cp &a){return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[N],b[N],c[N];
void FFT(cp s[],int len,int type)
{
    for(int i=0;i<len;i++)
        if(i<r[i]) swap(s[i],s[r[i]]);
    for(int k=2;k<=len;k<<=1)
    {
        cp wn(cos(2*pi*type/k),sin(2*pi*type/k));
        for(int i=0;i<len;i+=k)
        {
            cp t,w(1,0);
            for(int j=0;j<(k>>1);j++,w=w*wn)
            {
                t=w*s[i+j+(k>>1)];
                s[i+j+(k>>1)]=s[i+j]-t;
                s[i+j]=s[i+j]+t;
            }
        }
    }
}
void FFT_main(cp A[],cp B[],cp C[],int len)
{
    FFT(A,len,1);FFT(B,len,1);
    for(int i=0;i<len;i++) C[i]=A[i]*B[i];
    FFT(C,len,-1);
}

int gc()
{
    int rett=0,fh=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
    while(c>='0'&&c<='9'){rett=(rett<<3)+(rett<<1)+c-'0';c=getchar();}
    return rett*fh;
}

int main()
{
    n=gc(),m=gc(),ma=0,n++,m++;
    for(int i=0;i<n;i++) a[i].x=1.0*gc();
    for(int i=0;i<m;i++) b[i].x=1.0*gc();
    while((1<<ma)<n+m){ma++;}
    for(int i=0;i<(1<<ma);i++) 
        r[i]=(r[i>>1]>>1)|((i&1)<<(ma-1));
    FFT_main(a,b,c,1<<ma);
    for(int i=0;i<n+m-1;i++) printf("%d ",(int)(c[i].x/(1<<ma)+0.1));
    return 0;
}