有关多项式的一个基础算法，学起来比较困难。
快速傅里叶变换和傅里叶变换没什么关系，也不是傅里叶发明的。这种算法用于在 \(O(n\log n)\) 时间复杂度内求出两个多项式的卷积（相当于多项式相乘）。
前置知识
多项式的表示
\(n\) 项式等价于 \(n-1\) 次项式。（每个次项的系数都不为零）
系数表示法
形如 \(F(x)=\sum\limits^{n-1}_{i=0} a_ix^i\)，把一个 \(n-1\) 次项式的每一次项都表示出来。
两个多项式直接相乘时间复杂度为 \(O(n^2)\)。
点值表示法
对于一个 \(n-1\) 次多项式，可以用 \(n\) 个点 \((x_i,y_i=F(x_i)\) 来表示，可以证明这么表示不会表示为多个 \(n-1\) 次多项式。
当两个表示不同多项式的点 \(x\) 坐标相等，\(y\) 坐标直接相乘。这种情况下相乘时间复杂度为 \(O(n)\)。
两种表示法间的转换
系数表示法 \(\rightarrow\) 点值表示法
对于 \(n-1\) 次项式选取 \(n\) 个点计算对应值来表示。
点值表示法 \(\rightarrow\) 系数表示法
根据每个点列出 \(n-1\) 元方程，通过高斯消元解出方程。
注意在上述及下文的关于多个多项式的计算中，要统一次数，次数低的多项式要在高次上补零。