[模板] 快速傅里叶变换/FFT/NTT

简介

FFT是多项式乘法的一种快速算法, 时间复杂度 \(O(n \log n)\).

FFT可以用于求解形如\(C_i = \sum_{j=0}^i A_jB_{i-j}\)的式子. 如果下标有偏差,可以通过平移, 翻转等方法化为上式.

Code

const int nmax=(int)3e6+50;

const db pi=acos(-1.0);

struct tcpx{db a,b;}c1[nmax],c2[nmax];

tcpx operator+(tcpx a,tcpx b){return (tcpx){a.a+b.a,a.b+b.b};}

tcpx operator-(tcpx a,tcpx b){return (tcpx){a.a-b.a,a.b-b.b};}

tcpx operator*(tcpx a,tcpx b){return (tcpx){a.a*b.a-a.b*b.b,a.a*b.b+a.b*b.a};}

int l,rev[nmax];

void dft(tcpx *c,int n,int fl){

    rep(i,0,n-1)if(i<rev[i])swap(c[i],c[rev[i]]);

    for(int i=1;i<n;i<<=1){

        tcpx wn=(tcpx){cos(pi/i),fl*sin(pi/i)};

        for(int j=0,p=(i<<1);j<n;j+=p){

            tcpx w=(tcpx){1,0};

            for(int k=0;k<i;++k,w=w*wn){

                tcpx x=c[j+k],y=w*c[j+k+i];

                c[j+k]=x+y,c[j+k+i]=x-y;

            }

        }

    }

}

void fft(tcpx *c1,int n,tcpx *c2,int m,tcpx *c3){//c3=c1*c2; c3 could equal to c1/c2; cannot use c1 or c2 later

    m+=n,l=0;

    for(n=1;n<=m;n<<=1)++l;

    rep(i,0,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));

    dft(c1,n,1),dft(c2,n,1);

    rep(i,0,n-1)c3[i]=c1[i]*c2[i];

    dft(c3,n,-1);

    rep(i,0,n-1)c3[i].a=(c3[i].a/n);

}

//print as intager

    rep(i,0,n+m-2)cout<<(int)(c1[i].a+.5)<<' ';

https://www.cnblogs.com/ppprseter/p/10079353.html