快速傅立叶变换 FFT

理解原理推荐看算法导论。

附个图：
这里写图片描述

//代码学洛谷管理员的
typedef complex<double> C;
const double PI=acos(-1);

void FFT(int n,C a[],int f){
	for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
	for(int i=1;i<n;i<<=1){
		C wn(cos(PI/i),f*sin(PI/i));
		for(int j=0;j<n;j+=i<<1){
			C w(1,0);
			for(int k=0;k<i;k++,w*=wn){
				C x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y,a[j+k+i]=x-y;
			}
		}
	}
	if(f==-1) for(int i=0;i<n;i++) a[i]/=n;
}

int init(int n,int m){
	int l=0;
	m+=n;
	for(n=1;n<=m;n<<=1) l++;
	for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	return n;
}

##练习##
– 【BZOJ3771】Triple
– 【BZOJ3160】万径人踪灭

版权声明：本文为lsq647vsejgfb原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/lsq647vsejgfb/p/9354864.html