fft

__ryp__ · 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 的证明，还要补。