FFT

Fast Fourier Transform

多项式的点值表示法

所以，两个度数为 $n-1$ 的多项式 $f(x),g(x)$，其乘积 $h(x)$ 为 $2n-2$ 度的多项式 $h(x)=\sum_{i=0}^{2n-2} b_ix^i$

$h(x)$ 的点值表示法需要 $2n-1$ 个点，那么为了从 $f(x),g(x)$ 计算出 $h(x)$，我们也需要在 $f(x),g(x)$ 上取 $2n-1$ 个点。

而朴素的多项式乘法需要 $O(n^2)$，所以，只要我们可以用比 $O(n^2)$ 的方式计算出 $f(x),g(x)$ 上的 $2n-1$ 个点 $(x_i,f(x_i)),(x_i,g(x_i))$，然后再以 $O(n)$ 把点乘起来 $(x_i,f(x_i)\cdot g(x_i))$ 得到 $(x_i,h(x_i))$，再将 $h(x)$ 上的 $2n-1$ 个点转化成系数表示法，就大功告成了！

所以我们的思路是

用线性对数时间复杂度计算 Point-Value Representation

怎么以 $O(n\log n)$ 计算 $f(x)$ 的 $2n-1$ 个点值呢？考虑分治，令 $f(x)$ 的 Coefficient Representation 为

把 $f(x)$ 的系数分成偶数项和奇数项：

所以我们有

考虑两个点 $x_1,x_2$，如果我们不用任何优化，我们一共需要计算 $4$ 个值，才能计算出两个点值：$f_0(x_1^2),f_1(x_1^2),f_0(x_2^2),f_1(x_2^2)$.

然而，如果我们令 $x_1=-x_2$，也就是说 $x_1^2=x_2^2$，那么我们只需要计算 $2$ 个值，就可以计算出两个点值了：$f_0(x_1^2),f_1(x_1^2)$.

所以，令 $T(n)$ 表示计算 degree 为 $n$ 的 $f(x)$ 的点值，则

引入复数

上一节我们已经知道了，考虑 $n$ 个值 $x_0,x_1,x_2\dots, x_{n-1}$ 需要满足

然后进入递归，我们就需要对 $n/2$ 个值 $x_0^2,x_1^2,x_2^2\dots x_{n/2-1}^2$ 对应的点值 $f(x_0^2),f(x_1^2),f(x_2^2)\dots ,f(x_{n/2-1}^2)$

类似的，为了进一步递归下去，这 $n/2$ 个值也应该满足

这里就必须引入复数了（不然只能全部等于 $0$）。