FFT

一句话理解

FFT 快速傅里叶变换，O(n log n) 卷积。

为什么要学

多项式乘法。

讲解

单位根、蝶形运算、递归分治。

例子

点值相乘再插值。

常见错误

• n 不是 2 的幂没补 0。
• 浮点误差。