FFT

独秀平川 · 2018-06-09 20:09:02 · 个人记录

FFT(Fast Fast TLE)

和其他大佬一样的复数操作。

迭代过程：

///FFT
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
typedef double db;
const int inf=0x3f3f3f3f;
const int MAX=2e6+1e5;
const db pi=acos(-1.0);
struct complx
{
    db x,y;
    complx():x(0),y(0){}
    complx(db x,db y):x(x),y(y){}

};
complx operator + (complx a,complx b)
{
    return complx(a.x+b.x,a.y+b.y);
}
complx operator-(const complx &a,const complx &b)
{
    return complx(a.x-b.x,a.y-b.y);
}
complx operator*(const complx &a,const complx &b)
{
    return complx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
int n,m,lmt;
complx g[MAX],h[MAX];
void fft(complx *a,int len,int op)
{
    /*
    公式：f(pow(Wn,k))=f0(pow(Wn/2,k))+pow(Wn,k)*f1(pow(Wn/2,k))
    */
    //此排列顺序保证每次迭代时相邻的两块都是能推出f(x)的f0(pow(x,2))和f1(pow(x,2))
    static int num[MAX];
    int high=(log(len)+0.1)/log(2)-1;//最高位
    num[0]=0;
    for(int i=1;i<len;i++)
    {
        num[i]=(num[i>>1]>>1)|((i&1)*(1<<high));
        //将二进制位反过来的递推
    }
    for(int i=0;i<len;i++)
    {
        if(i<num[i])swap(a[i],a[num[i]]);
        //改变序列顺序 
    }
    for(int mid=1;mid<len;mid<<=1)
    {
        int r=(mid<<1);
        complx w1=complx(cos(pi/mid),sin(pi/mid)*op);//此时的Wx，即Wr
        for(int i=0;i<len;i+=r)
        {
            complx w=complx(1,0);
            for(int j=0;j<mid;j++)
            {
                //覆盖
                complx tmp=a[i+j];
                a[i+j]=tmp+a[i+mid+j]*w;
                a[i+mid+j]=tmp-a[i+mid+j]*w;
                w=w*w1;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)scanf("%lf",&g[i].x);
    for(int i=0;i<=m;i++)scanf("%lf",&h[i].x);
    lmt=1;
    while(lmt<=n+m)lmt<<=1;
    fft(g,lmt,1);fft(h,lmt,1);
    //求系数
    for(int i=0;i<lmt;i++)g[i]=g[i]*h[i];
    fft(g,lmt,-1);
    for(int i=0;i<=n+m;i++)
    {
        printf("%d ",(int)(g[i].x/lmt+0.1));
        //注：eps要在后面加，改成(g[i].x+0.1)/lmt会秘制WA掘机
    }
    return 0;
}