关于FFT的一些感想

FFT

卷积形式

h(n)=f(n)∗g(n) $$h(n)=f(n)\ast g(n)$$

h(n)=∑i=1nf(i)×g(n−i) $$h(n)=\underset{i=1}{\overset{n}{\sum }}f(i)\times g(n-i)$$

用途

快速计算卷积

具体实现

这里不再赘述，这里有详尽的解释，其性质主要利用单位复根的特殊性。
主要的公式为：

Win=Wi/2n/2 $$W_n^i=W_{n/2}^{i/2}$$

f(x)=f(x2odd)+x×f(x2even) $$f(x)=f(x_{odd}^2)+x\times f(x_{even}^2)$$

附上精美代码一份

#include<bits/stdc++.h>
#ifdef WIN32
#define lld I64d
#endif
#define il inline
#define rg register 

using namespace std ;

typedef long long LL;
typedef double LF;

const int inf=2147483647;
const LF eps=1e-8;
const LF pi=acos(-1.0);
const LL INF=9223372036854775807;

struct cpx
{
    LF x,y;
    cpx (){}
    cpx (LF xx,LF yy):x(xx),y(yy){}
};

il cpx operator + (cpx a,cpx b) { return cpx(a.x+b.x,a.y+b.y); }
il cpx operator - (cpx a,cpx b) { return cpx(a.x-b.x,a.y-b.y); }
il cpx operator * (cpx a,cpx b) { return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }

LF Abs(LF x) {return x>0?x:-x;}

il int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int MAXN=1e7+10;
int N,M,n,m,rev[MAXN];
cpx a[MAXN],b[MAXN];

il void fft(cpx *A,int f)
{
    for (int i=0;i<N;i++)
        if (i<rev[i])
            swap(A[i],A[rev[i]]);
    for (int mid=1;mid<N;mid<<=1)
    {
        cpx Wn(cos(pi/mid),f*sin(pi/mid));
        for (int r=mid<<1,j=0;j<N;j+=r)
        {
            cpx w(1,0);
            for (int k=0;k<mid;k++,w=w*Wn)
            {
                cpx x=A[j+k],y=w*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
    if (f==-1)
        for (int i=0;i<N;i++)
            a[i].x/=N;
}

int main()
{

    #ifndef ONLINE_JUDGE
    freopen("fft.in","r",stdin);
    freopen("fft.out","w",stdout);
    #endif
    n=read(),m=read();
    for (int i=0;i<=n;i++) a[i].x=read();
    for (int i=0;i<=m;i++) b[i].x=read();

    for (N=1;N<=n+m;M++) 
        N<<=1;
    for (int i=0;i<N;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(M-1));

    fft(a,1);
    fft(b,1);
    for (int i=0;i<=N;i++)
        a[i]=a[i]*b[i];

    fft(a,-1);
    for (int i=0;i<=n+m;i++)
        printf("%d ",(int)(a[i].x+0.5));

    return 0;
}

一些想法

fft主要是用来快速计算卷积，卷积的形式上面有提到。这种形式非常像暴力枚举，如果把g函数倒转，就变成了按位相乘。并不是真的按位相乘，类似于乘法，是对应位相乘。

大致是这种模样：

h(n)=∑i=1nf(i)×g(n−i)（翻转前） $$h(n)=\underset{i=1}{\overset{n}{\sum }}f(i)\times g(n-i)（翻转前）$$

h(n)=∑i=1nf(i)×g(i+(N−n))（翻转后1） $$h(n)=\underset{i=1}{\overset{n}{\sum }}f(i)\times g(i+(N-n))（翻转后1）$$

h(N−a)=∑i=1N−af(i)×g(i+a)（翻转后2） $$h(N-a)=\underset{i=1}{\overset{N-a}{\sum }}f(i)\times g(i+a)（翻转后2）$$

满足这条式子还需要{f}与{g}的长度相等(N)
这样的表达方式就比较类似于按位比较之类的方法。

如果用图片说明：

这个是{f}的顺序

这个是{g}翻转前的顺序

这个是{g}翻转后的顺序

现在我把{f}与{g}翻转后的图片放在一起

看了这张图片，有没有觉得视野忽然开阔了许多？这样的模型可以用来解决其他很多问题。（请dalao不要吐槽，对于一个初学者来说，这不是基本操作）

没错，BB了这么久，我就是想说——这样的fft就能够解决一些字符串间的匹配问题啦！

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4259

最后，我只想说：我太菜了，推不出这题的式子，所以只好分享一下一些新奇的思路。