本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-31 23:37:49

多项式基本中的基本就是著名的 FFT。这个东西一个简单的（也是我现在只会的）用途是做多项式的乘法。

如果能做到两个过程 —— 即给定 $n$ 次多项式，求其在 $n$ 个不同点上的取值；给定 $n$ 个点表示某多项式的某些取值，还原出这个多项式 —— 我们就能快速进行多项式乘法：因为只需要把第一个过程得到的 $n$ 个点上的取值乘起来，然后还原，就好了。

DFT 就是解决这个东西的。我还分不清它和 FFT 的区别，暂且就这么叫着。

首先考虑怎么做第一步。

给定了多项式 $f(x) = \sum\limits_{i=0}^n a_ix$，要求其在 $n$ 个固定点上的取值。

设 $f_0(x)$ 表示这个多项式的偶数项取出来后得到的多项式（次数减半），$f_1(x)$ 表示相应的次数为奇数的。那么 $f(x) = f_0(x^2) + xf_1(x^2)$。这样分治下去，好像很对，但是啥用也没有，因为我们只是知道这两个子多项式在 $n/2$ 个点上的取值，无法解决现在的问题。

考虑：$f(-x) = f_0(x^2) - xf_1(x^2)$。很有启发性啊！这样，递归到 $f_0$ 和 $f_1$ 后，就可以 $O(n)$ 得到 $n$ 个点的取值了。

但是，相反数只有一对，肯定不能按来按去一直用。这个时候考虑把视角放到复数。设 $\omega_n^k = \exp (2\pi k\text{i} / n)$，那么有 $(\omega_n^k)^2 = \omega_{n/2}^k$。这个构造性确实很强，因为递归到子问题时，底标恰好也减半。同时，有 $\omega_n^{k+n/2} = -\omega_n^k$，因此恰好可以把它代入到原式里头。

得到：$f(\omega_n^k) = f_0(\omega_{n/2}^k) + \omega_n^k f_1(\omega_{n/2}^k)$

与：$f(\omega_n^{k+n/2}) = f_0(\omega_{n/2}^k) - \omega_n^k f_1(\omega_{n/2}^k)$。

就可以了。复杂度是线性单对数。

然后是第二步，怎么还原回去呢？经过我还没看的代数推导，只需要把 $f_1$ 前面的系数指数变成负的，最后把所有东西除以一个 $n$，就好了。

待补充：递归转迭代，IFFT 的证明，还有 NTT。

补充：递归转迭代，观察一下就好了。NTT，把 $\omega$ 的定义换一下就好了。IFFT 的证明，还要补。