• FFT
  • 推荐博客
  • 大致流程
  • 复数
    • 运算
  • DFT
    • 单位根（n等分）
    • 性质
  • FFT
  • IFFT
  • 递归版
  • 迭代版（蝴蝶变化）

FFT

推荐博客

快速傅里叶变换（FFT）超详解

浅谈 FFT （终于懂一点了~~）

十分简明易懂的FFT（快速傅里叶变换）

题目链接：P3803 【模板】多项式乘法（FFT）

大致流程

系数表示法<--O(NlongN)-->点值表示法

点值表示法O(n):对应点的函数值相乘

复数

共轭复数：a+bi，a-bi

运算

z1+z2=(a+c)+(b+d)i

z1z2=(ac-bd)+(ad+bc)i=(a1a2,θ1+θ2)(另一种形式，模长相乘，极角相加)

DFT

单位根（n等分）

\((w^1_n)^k=w^k_n\)

\(w^k_n=cos\frac{k}{n}2\pi+isin\frac{k}{n}2\pi\)

带入的x是\(w_n^{0,1,2...n-1}\)

性质

\(w^k_n=w^{2k}_{2n}\)

\(w^{k+\frac{n}{2}}_n=w^{k}_{n}\)

\(w^0_n=w^{n}_{n}\)

FFT

IFFT

将FFT中的\(w^k_n\),改为它的共轭复数

递归版

#include<bits/stdc++.h>
#define Fu(i,a,b) for(register int i=(a);i<=(b);i++)
#define cp complex<double>
using namespace std;
const double pi=acos(-1.0);
int n,m,len=1,x;
cp a[8000005],b[8000005];
void fft(int n,cp *a,int inv){
	if(n==1) return ;
	cp b[n];
	int mid=n>>1;
	Fu(i,0,mid-1) b[i]=a[i*2],b[i+mid]=a[i*2+1];
	Fu(i,0,n-1) a[i]=b[i];
	fft(mid,a,inv),fft(mid,a+mid,inv);
	Fu(i,0,mid-1){
		cp x(cos(i*2*pi/n),inv*sin(i*2*pi/n));
		b[i]=a[i]+x*a[i+mid],b[i+mid]=a[i]-x*a[i+mid];
	}
	Fu(i,0,n-1) a[i]=b[i];
}
int main(){
	scanf("%d%d",&n,&m);
	Fu(i,0,n) scanf("%d",&x),a[i].real(1.0*x);
	Fu(i,0,m) scanf("%d",&x),b[i].real(1.0*x);
	while(len<=n+m) len<<=1;
	fft(len,a,1),fft(len,b,1);
	Fu(i,0,len) a[i]*=b[i];
	fft(len,a,-1);
	Fu(i,0,n+m) printf("%.0f ",a[i].real()/len+0.49);
	return 0;
}

迭代版（蝴蝶变化）

快速傅里叶变换（FFT）的优化

可以发现\(w^i_n\)在最终的序列中的位置下标相当于\(i\)二进制下翻转得到的数。

Fu(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));

#include<bits/stdc++.h> //三次变二次+预处理三角函数+蝴蝶变化 
#define Fu(i,a,b) for(register int i=(a);i<=(b);i++)
#define cp complex<double>
using namespace std;
const double pi=acos(-1.0);
double ccos[8000005],ssin[8000005]; 
int n,m,len=1,x,rev[8000005],bit;
cp a[8000005],b[8000005];
void fft(int n,cp *a,int inv){
	Fu(i,0,n) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int mid=1;mid<n;mid<<=1){
		cp wn(ccos[mid],inv*ssin[mid]);
		for(int i=0;i<n;i+=mid<<1){
			cp w0(1,0);
			Fu(j,0,mid-1){
				cp x=a[i+j],y=w0*a[i+j+mid];
				a[i+j]=x+y,a[i+j+mid]=x-y,w0*=wn;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	Fu(i,0,n) scanf("%d",&x),a[i].real(1.0*x);
	Fu(i,0,m) scanf("%d",&x),a[i].imag(1.0*x);
	while(len<=n+m) len<<=1,bit++,ccos[len]=cos(pi/len),ssin[len]=sin(pi/len);
	Fu(i,0,len) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	fft(len,a,1);
	Fu(i,0,len) a[i]*=a[i];
	fft(len,a,-1);
	Fu(i,0,n+m) printf("%.0f ",a[i].imag()/2/len+0.49);
	return 0;
}