FFT 学习笔记（施工中）

FFT 功能

快速傅里叶变换， 时间复杂度快速完成点值表达式和系数表达式的转换。一般搭配生成函数等等食用。

由于点值表达式相乘大大快于多项式卷积，所以先将多项式通过 转化为点值表达式，对应点（单位根处的值）相乘后使用 转化回多项式的形式。

基本公式

其中 是一个 次多项式， 和 分别是 取出偶次项和奇次项形成的多项式。具体过程：

所以：

至此推导完毕。借助上述公式，我们可以实现点值表达式的合并，即我们可以从 和 的点值表达式

算法流程

设我们当前需要做乘法的多项式为 和 ，首先将它们的次数补齐至 的若干次方。接下来，