sxczf's Blog

蒟蒻自己的一点理解，求轻喷……

附上FFT的百度百科http://baike.baidu.com/subview/7562/9485379.htm?fr=aladdin

维基百科http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2

其实百科没什么用……

介绍什么的就省去了……

《算法导论》上有详细的证明，但是显然很难看懂……

怎么办呢？好吧，我只会背代码……

经过大神syc的介绍以及和小伙伴luguoshan认真的学习，只看懂了一点点……

首先要把代码背熟……保证在10分钟之内写出{pre过程和FFT过程}（模板）……

然后把题目转化为卷积式，像ans[i]=Σa[j]*b[n-j](0<=j<=i)然后把模板啪上去题目就解决了……

换句话说，FFT可以在nlogn的时间范围内计算卷积的答案

注意点：常数较大，数组要开题目给定n的4倍，计算过程为实数，结尾如果转整数要加0.5（四舍五入）

附FFT模板：

struct node{double x,y;}a[400005],b[400005],w[2][400005];
node operator +(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};}
node operator *(node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
void pre(){
	for(i=0;i<N;i++)
	for(int j=1,x=i;j<N;j<<=1,x>>=1)(rev[i]<<=1)|=(x&1);
	for(i=0;i<N;i++){
		double e=2.0*pi*i/N;
		w[0][i]=(node){cos(e),sin(e)};
		w[1][i]=(node){cos(e),-sin(e)};
	}
}
void FFT(node *A,int f){
	for(int i=0;i<N;i++)if (rev[i]>i)swap(A[rev[i]],A[i]);
	for(int i=1;i<N;i<<=1)
	for(int j=0,t=N/(i<<1);j<N;j+=i<<1)
	for(int k=0,l=0;k<i;k++,l+=t){
		node p=w[f][l]*A[j+k+i];
		node q=A[j+k];
		A[j+k]=q+p;
		A[j+k+i]=q-p;
	}
	if (f) for(int i=0;i<N;i++)A[i].x/=N;
}

pi就不用我解释了吧acos(-1)

scanf("%d",&n);
for(N=1;N<n;N<<=1);N<<=1;
for(i=0;i<n;i++)scanf("%d",&data[i]);
pre();

FFT中，我们使用的是N而不是n，所以数组4倍

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

看不懂？你需要一本《算法导论》

for(i=0;i<n;i++)ans[i]=(int)(a[i].x+0.5);

答案存在a.x中