【模板】FFT

佚名 6年前 (2019-05-04) 随笔 946人围观抢沙发百度已收录

FFT 的本质是在 \(O(nlogn)\) 的时间内进行点值表达和系数表达之间的转换，并在 \(O(n)\) 的时间内计算结果，故总时间复杂度为 \(O(logn)\)。
FFT注意事项

由于 tot 采用的是倍增的方式，因此实际内存开销可能是 \(2(n+m)\)。
a 和 b 数组中系数的存放顺序必须从低位到高位。(目前还不懂为什么)
多项式的项数和次数不同。

代码如下

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
const double pi=acos(-1);

int n,m;
struct cp{
    double x,y;
    cp(double xx=0,double yy=0):x(xx),y(yy){}
    friend cp operator+(const cp &a,const cp &b){return cp(a.x+b.x,a.y+b.y);}
    friend cp operator-(const cp &a,const cp &b){return cp(a.x-b.x,a.y-b.y);}
    friend cp operator*(const cp &a,const cp &b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
}a[maxn],b[maxn];
int rev[maxn],tot=1,bit;

void fft(cp *t,int flag){
    for(int i=0;i<tot;i++)if(i<rev[i])swap(t[i],t[rev[i]]);
    for(int mid=1;mid<tot;mid<<=1){
        cp wn(cos(pi/mid),flag*sin(pi/mid));
        for(int j=0,len=mid<<1;j<tot;j+=len){
            cp w(1,0);
            for(int k=0;k<mid;k++,w=w*wn){
                cp x=t[j+k],y=w*t[j+mid+k];
                t[j+k]=x+y,t[j+mid+k]=x-y; 
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)scanf("%lf",&a[i].x);
    for(int i=0;i<=m;i++)scanf("%lf",&b[i].x);
    while(tot<=n+m)tot<<=1,++bit;
    for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    
    fft(a,1),fft(b,1);
    for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=0;i<=n+m;i++)printf("%d ",(int)(a[i].x/tot+0.5));
    
    return 0;
}