快速傅立叶变换 FFT

快速傅立叶变换 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】万径人踪灭