原创 数学】快速傅里叶变换（FFT）

FFT 是之前学的，现在过了比较久的时间，终于打算在回顾的时候系统地整理一篇笔记，有写错的部分请指出来啊 qwq。

卷积、旋积或褶积（英语：Convolution）是通过两个函数 ff 和 gg​​ 生成第三个函数的一种数学算子。

设 f,gf,g​ 在 R1R1​ 上可积，那么 h(x)=∫∞−∞f(τ)g(x−τ)dτh(x)=∫−∞∞f(τ)g(x−τ)dτ 称为 ff 与 gg​ 的卷积。

对于整系数多项式域，n−1n−1 次多项式 A,BA,B 的卷积 h(x)=A(x)B(x)=∑ni=0∑ij=0aibi−jh(x)=A(x)B(x)=∑i=0n∑j=0iaibi−j。​

即用多项式各项系数来刻画这个多项式，例如 n−1n−1 次多项式就可以写成这样：A(x)=a0+a1x+...+an−1xn−1A(x)=a0+a1x+...+an−1xn−1

我们知道，nn​​​​ 个不同的点可以确定一个 n−1n−1​​​​ 次的多项式，所以我们可以使用 nn​​​​ 个（不同）点来刻画一个 n−1n−1​​​​ 次多项式。

这样做会有什么方便呢？

例如 f(x)=(x0,f(x0)),...(xn,f(xn)),g(x)=(x0,g(x0)),...(xn,g(xn))f(x)=(x0,f(x0)),...(xn,f(xn)),g(x)=(x0,g(x0)),...(xn,g(xn))，那么它们的卷积 h(x)=(x0,f(x0)g(x0)),...(xn,f(xn)g(xn))h(x)=(x0,f(x0)g(x0)),...(xn,f(xn)g(xn))。

这意味着在系数表示法中需要 O(n2)O(n2) 次的乘法运算在点值表示法中只需要 O(n)O(n) 次。

下面考虑如何将 n−1n−1 次多项式从系数表示法转为点值表示法。

因为用普通的方法选取 nn​​​​​ 个点然后将系数表示法转为点值表示法的复杂度为 O(n2)O(n2)​​​​​（因为需要选 nn​​​​​ 个点，然后对于每个点 xx 需要计算共 nn 项的结果），我们考虑如何优化这一步。

注意到满足 wn=1wn=1​​ 的单位根 ww​ 有 nn​ 个，故从这里入手。

我们记方程 wn=1wn=1 的第 kk 个单位根为 wknwnk​。

方便起见，设 nn​ 为 22​ 的幂（就算不是也可以看作是高次项的系数为 00​）。

将 A(x)A(x) 按照次数的奇偶性分别分成两组 F(x),G(x)F(x),G(x)，并表示为 A(x)=F(x2)+xG(x2)A(x)=F(x2)+xG(x2)

例如 A(x)=a0+a1x+a2x2+a3x3A(x)=a0+a1x+a2x2+a3x3​，那么 F(x)=a0+a2x,G(x)=a1+a3xF(x)=a0+a2x,G(x)=a1+a3x​。

将 x=wknx=wnk​ 代入 A(x)A(x)​，由复数的性质，

A(wkn)=F(wkn2)+wknG(wkn2)A(wnk)=F(wn2k)+wnkG(wn2k)​ ，类似地 A(wk+n2n)=F(wkn2)−wknG(wkn2)A(wnk+n2)=F(wn2k)−wnkG(wn2k)​。​

推导：

A(wk+n2n)=F(w2k+nn)+wk+n2nG(w2k+nn)=F(wkn2)+wk+n2nG(wkn2)=F(wkn2)−wknG(wkn2)A(wnk+n2)=F(wn2k+n)+wnk+n2G(wn2k+n)=F(wn2k)+wnk+n2G(wn2k)=F(wn2k)−wnkG(wn2k)​​​

可以发现对于两个相应的单位根 wkn,wn2+knwnk,wnn2+k​，可以用对应的 F,GF,G​ 算出（可以递归地实现这个过程），而且计算的范围折半，所以一共需要计算 O(logN)O(logN)​ 层，每一层执行 O(n)O(n)​ 次运算，所以复杂度为 O(NlogN)O(NlogN)​。

下面考虑如何将 n−1n−1​ 次多项式从点值表示法转为系数表示法。

因为对于每个点值 yi=∑n−1k=0wkinyi=∑k=0n−1wnki，其中 i∈[0,n−1]i∈[0,n−1]​​​​，我们可以写出等式：

现在我们已经有向量 yy​​ 了（就是右式），因此，如果要得到向量 aa​​，只需要两边乘上 ww​​​ 矩阵的逆即可。

这里的 ww​​ 矩阵正是著名的范德蒙矩阵，它的逆正好是每一项都取倒数，然后除以 nn​​。

因此有 ai=1n∑n−1k=0w−kinai=1n∑k=0n−1wn−ki，其中 i∈[0,n−1]i∈[0,n−1]​。

有没有发现 ai,yiai,yi​ 的形式非常接近？据此，我们可以在实现的时候在同一个函数中写出逆变换和正变换，然后在得到的结果 res 中除以 nn 就可以了。（参照下面的代码）

至此，FFT 的基本原理讲述完毕，下面是优化。

按照上文的讲述，如果不看下面的代码，那么编写出来的是递归版本，但是这个版本的常数太大了，因此运行起来的效果不好，故使用位逆序置换来降低常数。

我们看看递归过程是什么样的，以 n=8n=8 为例：

这里就有一个非常神奇的规律：在最后一行中，原下标所对应的二进制数翻转正好是在最后一行的序数。例如 x6x6 的下标是 6=110(2)6=110(2)，那么它的序数正好是 011(2)=3011(2)=3。

据此，可以处理出 rev 数组，它记录的正是最后一行所有元素对应的下标。

简单地说，递归形式是自上而下地做 FFT，而利用位逆序置换我们可以自下而上地做 FFT，它们在实际运行中有着常数上的区别。

https://www.luogu.com.cn/problem/P3803

给定一个 nn 次多项式 F(x)F(x)，和一个 mm 次多项式 G(x)G(x)。

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