关于FFT的一些感想

时间:2022-02-05 01:34:38

FFT

卷积形式

h ( n ) = f ( n ) g ( n )

h ( n ) = i = 1 n f ( i ) × g ( n i )

用途

快速计算卷积

具体实现

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

W n i = W n / 2 i / 2

f ( x ) = f ( x o d d 2 ) + x × f ( x e v e n 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 = 1 n f ( i ) × g ( n i )

h ( n ) = i = 1 n f ( i ) × g ( i + ( N n ) ) 1

h ( N a ) = i = 1 N a f ( i ) × g ( i + a ) 2

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

如果用图片说明:

这个是{f}的顺序
关于FFT的一些感想

这个是{g}翻转前的顺序
关于FFT的一些感想

这个是{g}翻转后的顺序
关于FFT的一些感想

现在我把{f}与{g}翻转后的图片放在一起
关于FFT的一些感想

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

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

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

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