发现一个多项式卷积 FFT 的优化方式

一般来说，如果我们要求出 $F\left(x\right)$ 和 $G\left(x\right)$ 的卷积，会把它们分别 FFT ，然后对应每项乘起来，最后再 IFFT 回来。

但是我们可以合成一个新函数 $H\left(x\right) = F\left(x\right) + iG\left(x\right)$，求出 $H^2\left(x\right)$，然后把它的的虚部取出来除以 $2$ 就行了。

证明：
$$\left(a + bi\right)^2 = \left(a^2 - b^2\right) + 2abi$$

这样常数就只有原来的 $\dfrac23$ 了。

貌似比 NTT 快。

---

• 分类： 学习笔记
• 最后更新于：2023-10-23 08:47:04^UTC+8
• 标签： 多项式 FFT 常数优化