FFT的板子

shadowice1984 · 2018-04-04 19:58:48 · 个人记录

这里是给shadowice1984自用的板子

所以不会有很详细的解释呢……

tips:注意反转置换的计算细节以及计算二进制位长度的+1-1问题

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;const int N=262150;typedef double db;const db pi=acos(-1);
int n;int rn;int rv[N];int len;
struct cmp
{
    db r;db v;cmp(db R,db V){r=R;v=V;}
    friend cmp operator +(cmp a,cmp b){return cmp(a.r+b.r,a.v+b.v);}
    friend cmp operator -(cmp a,cmp b){return cmp(a.r-b.r,a.v-b.v);}
    friend cmp operator *(cmp a,cmp b){return cmp(a.r*b.r-a.v*b.v,a.r*b.v+a.v*b.r);}
    void operator /=(const db b){r/=b;v/=b;}
}a[N];
inline void fft(cmp* a,int n,db op)
{
    for(int i=0;i<n;i++){if(i<rv[i]){swap(a[i],a[rv[i]]);}}
    for(int k=1;k<n;k<<=1)
        for(int s=0;s<n;s+=k<<1)
        {
            cmp w(1,0);cmp rt(cos(pi/k),op*sin(pi/k));
            for(int i=s;i<s+k;i++,w=w*rt)
            {cmp ev=a[i];cmp od=a[i+k];a[i]=ev+w*od;a[i+k]=ev-w*od;}    
        }
    if(op==-1){for(int i=0;i<n;i++){a[i]/=n;}}
}
inline void clacrv()
{
    for(;(1<<len)<=rn;len++);n=1<<len;len--; 
    for(int i=0;i<n;i++){rv[i]=rv[i>>1]>>1|((i&1)<<len);}
}