快速傅里叶变换

参考资料

• 快速傅里叶变换 - OI Wiki

思想

快速傅里叶变换（Fast Fourier Transform，FFT）在 $O(n\log n)$ 内计算两个多项式的乘积。它把多项式在 $n$ 个单位根 $\omega_n=e^{2\pi i/n}$ 处求值（DFT），逐点相乘后再插值还原（IDFT）；利用单位根的折半性质分治，把朴素 $O(n^2)$ 的 DFT 降到 $O(n\log n)$。求多项式乘法时，对两个多项式做正变换、逐位相乘、再做逆变换即得结果。

实现

分治递归

按下标奇偶把多项式拆成两半递归，直接对应 DFT 的分治定义。

398 Bcpp

void fft(Comp *f,int n,int type)
{
	if(n==1)return;
	int mid=n>>1;
	Comp *g=f,*h=f+mid;
	for(int i=0;i<n;i++)t[i]=f[i];
	for(int i=0;i<mid;i++)
	{
		g[i]=t[i<<1];
		h[i]=t[i<<1|1];
	}
	fft(g,mid,type);
	fft(h,mid,type);
	Comp cur(1,0),step(cos(pi*2/n),sin(pi*2/n)*type);
	for(int i=0;i<mid;i++)
	{
		t[i]=g[i]+cur*h[i];
		t[i+mid]=g[i]-cur*h[i];
		cur=cur*step;
	}
	for(int i=0;i<n;i++)f[i]=t[i];
}

倍增迭代

先按二进制位逆序置换，再自底向上合并，避免递归、常数更小，是常用写法。

329 Bcpp

void fft(Comp *f,int n,int type)
{
	for(int i=0;i<n;i++)if(i<r[i])swap(f[i],f[r[i]]);
	for(int k=1;k<n;k<<=1)
	{
		Comp step(cos(pi/k),sin(pi/k)*type);
		for(int i=0;i<n;i+=k<<1)
		{
			Comp cur(1,0);
			for(int j=0;j<k;j++)
			{
				Comp x=f[i+j],y=f[i+j+k]*cur;
				f[i+j]=x+y;
				f[i+j+k]=x-y;
				cur=cur*step;
			}
		}
	}
}

例题

洛谷 P3803 【模板】多项式乘法（FFT）

给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$。

请求出 $F(x)$ 和 $G(x)$ 的乘积。

洛谷 P1919 【模板】高精度乘法 | A*B Problem 升级版

给你两个正整数 $a,b$，求 $a\times b$。（$1\le a,b\le 10^{1000000}$）