简介

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
    
     >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)<<' ';