信息里的 FFT 指的是快速（离散）傅里叶变换，用来把一个多项式 $O(n\log n)$ 地用点值法来表示，因此可以用来做多项式乘法。与物理上（连续的）傅里叶变换有所区别（我之前一直以为和物竞里的是一回事）。

引入

如果我们有两个 $n$ 次的多项式，我们如何计算这两个多项式相乘呢？
首先，朴素地计算是 $O(n^2)$ 的，好慢啊。我们先从单个多项式入手。

多项式的点值表示

通过拉格朗日插值法或者方程组，我们知道 $n+1$ 个点能确定一个 $n$ 次多项式（