FFT（快速傅立叶变换）在数字图像处理、计算机网络等领域都有广泛应用，但在算法竞赛中，它主要用于解决多项式乘法、生成函数相关的题目。本教程将从多项式基础出发，逐步深入 DFT 和 FFT 的原理，并给出可直接使用的 C++ 模板和典型例题解析。

1. 多项式基础

1.1 表达方式

简介

• 系数表达式：即 $A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-1} x^{n-1}$，用 $n$ 个系数表示。
• 点值表达式：用 $n$ 个不同的 $(x_i, y_i)$ 坐标表示，其中 $y_i = A(x_i)$。要确定一个 $n-1$ 次多项式，需要 $n$ 个不同的点。

比较

• 对于系数表示，多项式加法的时间复杂度是 $O(n)$，多项式乘法（暴力）的时间复杂度是 $O(n^2)$。
• 对于点值表示，多项式加法的时间复杂度同样为 $O(n)$，但乘法的时间复杂度仅为 $O(n)$——因为两个 $n-1$ 次多项式相乘后最高为 $2n-2$ 次，只需要 $2n-1$ 个点值对应相乘即可。