FFT
卷积形式
用途
快速计算卷积
具体实现
这里不再赘述,这里有详尽的解释,其性质主要利用单位复根的特殊性。
主要的公式为:
附上精美代码一份
#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函数倒转,就变成了按位相乘。并不是真的按位相乘,类似于乘法,是对应位相乘。
大致是这种模样:
满足这条式子还需要{f}与{g}的长度相等(N)
这样的表达方式就比较类似于按位比较之类的方法。
如果用图片说明:
这个是{f}的顺序
这个是{g}翻转前的顺序
这个是{g}翻转后的顺序
现在我把{f}与{g}翻转后的图片放在一起
看了这张图片,有没有觉得视野忽然开阔了许多?这样的模型可以用来解决其他很多问题。(请dalao不要吐槽,对于一个初学者来说,这不是基本操作)
没错,BB了这么久,我就是想说——这样的fft就能够解决一些字符串间的匹配问题啦!
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4259
最后,我只想说:我太菜了,推不出这题的式子,所以只好分享一下一些新奇的思路。