FFT 和生成函数

多项式乘法

问题背景

给定两个多项式 $A(x)$ 和 $B(x)$：

$$\begin{gathered} A(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_n{x}^n\text{ \\ B(x)=b0+b1x+b2x2+⋯+bmxm} \end{gathered}$$

我们需要计算它们的乘积 $C(x)=A(x)\cdot B(x)$。

根据定义，乘积 $C(x)$ 的系数 $c_k$ 为：$c_k=\sum _{i=0}^k{a}_i{b}_{k-i}$。这个形式的计算被称为卷积。如果我们直接按照这个定义进行计算，对于 $C(x)$ 的每一项系数，都需要 $O(k)$ 的时间。由于 $C(x)$ 的最高次项为 $n+m$，总的时间复杂度为 $O((n+m{)}^2)$，通常简记为 $O(n^2)$。当 $n$ 和 $m$ 的规模达到 ${10}^5$ 甚至更大时，这种朴素算法显然无法接受。

加速计算的思路：点值表示法

我们知道，一个 $n$ 次多项式可以被 $n+1$ 个不同的点唯一确定。例如，一条直线（1 次多项式）可以被两个点唯一确定，一条抛物线可以被三个点唯一确定。

这启发我们，除了用系数表示多项式，还可以用点值来表示。

• 系数表示法：$A(x)=\sum _{i=0}^n{a}_i{x}^i$
• 点值表示法：给定 $n+1$ 个不同的数 $x_0,x_1,\dots ,x_n$，计算出 $y_i=A(x_i)$，则多项式 $A(x)$ 可以用点对集合 $\text{set(x\_0, y\_0), (x\_1, y\_1), dots, (x\_n, y\_n)}}$ 来表示。

点值表示法的优势在于乘法运算。如果 $C(x)=A(x)\cdot B(x)$，那么对于任意一个 $x_i$，显然有 $C(x_i)=A(x_i)\cdot B(x_i)$。因此，如果 $A(x)$ 和 $B(x)$ 都在一组相同的点 $\text{setx\_0, x\_1, dots, x\_{n+m}}}$ 上求值，我们就可以在 $O(n+m)$ 的时间内计算出 $C(x)$ 在这些点上的点值。

这给了我们一个全新的计算流程：

1. 求值（Evaluation）：选择 $n+m+1$ 个点，分别计算出 $A(x)$ 和 $B(x)$ 在这些点上的点值。
2. 点积（Pointwise Product）：将 $A(x)$ 和 $B(x)$ 的点值对应相乘，得到 $C(x)$ 的点值。
3. 插值（Interpolation）：根据 $C(x)$ 的点值，反解出它的系数。

这个思路的关键在于如何快速地完成第一步（求值）和第三步（插值）。如果随机选取点，求值过程的复杂度依然是 $O(n^2)$。因此，我们需要找到一组特殊的点，使得求值和插值可以被加速。

快速傅里叶变换（FFT）

快速傅里叶变换（Fast Fourier Transform, FFT）就是实现上述快速求值和插值的关键算法。它巧妙地选取了一组特殊的复数——单位根，作为求值的点。

复数与单位根

• 复数：形如 $a+bi$ 的数，其中 $a$ 是实部， $b$ 是虚部，$i$ 是虚数单位，满足 $i^2=-1$。复数可以在复平面上表示，对应坐标为 $(a,b)$。
• 欧拉公式：$e^{i\theta }=\cos (\theta )+i\sin (\theta )$。这建立了指数函数和三角函数之间的桥梁，几何意义是复平面上一个模长为 1，与正实轴夹角为 $\theta$ 的向量。
• $n$ 次单位根：满足方程 $z^n=1$ 的复数解 $z$。根据欧拉公式，这些解恰好有 $n$ 个，它们是：$${\omega }_n^k=e^{i\frac{2\pi k}{n}}=\cos \left(\frac{2\pi k}{n}\right)+i\sin \left(\frac{2\pi k}{n}\right)(k=0,1,\dots ,n-1)$$其中 ${\omega }_n^k$ 表示第 $k$ 个 $n$ 次单位根。

单位根在复平面上均匀地分布在一个单位圆上，它们把圆 $n$ 等分。

单位根的性质：

1. 周期性：${\omega }_n^{k+n}={\omega }_n^k$
2. 对称性：${\omega }_n^{k+\frac{n}{2}}=-{\omega }_n^k$（当 $n$ 为偶数）
3. 折半引理：$({\omega }_n^k{)}^2={\omega }_{\frac{n}{2}}^k$（当 $n$ 为偶数）

1.3.2 FFT 的分治思想

FFT 的核心思想是分治。假设我们要对一个 $n-1$ 次多项式 $A(x)=\sum _{i=0}^{n-1}{a}_i{x}^i$ 在 $n$ 个单位根 ${\omega }_n^0,\dots ,{\omega }_n^{n-1}$ 上求值（这里假定 $n$ 是 2 的幂，不足则高位补 0）。

我们将 $A(x)$ 按系数的奇偶性分成两部分：

令 $A_0(y)=a_0+a_{2}y+a_4{y}^2+\dots ,A_1(y)=a_1+a_{3}y+a_5{y}^2+\dots$

则有

$$A(x)=A_0(x^2)+x{A}_1(x^2)$$

现在，我们要在 $x={\omega }_n^k$ 处求值：

$$A({\omega }_n^k)=A_0(({\omega }_n^k{)}^2)+{\omega }_n^k{A}_1(({\omega }_n^k{)}^2)$$

利用折半引理 $({\omega }_n^k{)}^2={\omega }_{\frac{n}{2}}^k$，上式变为：

$$A({\omega }_n^k)=A_0({\omega }_{\frac{n}{2}}^k)+{\omega }_n^k{A}_1({\omega }_{\frac{n}{2}}^k)$$

对于 $k+\frac{n}{2}$ 的情况：

$$A({\omega }_n^{k+\frac{n}{2}})=A_0({\omega }_{\frac{n}{2}}^{k+\frac{n}{2}})+{\omega }_n^{k+\frac{n}{2}}{A}_1({\omega }_{\frac{n}{2}}^{k+\frac{n}{2}})$$

利用周期性和对称性 ${\omega }_{\frac{n}{2}}^{k+\frac{n}{2}}={\omega }_{\frac{n}{2}}^k$ 和 ${\omega }_n^{k+\frac{n}{2}}=-{\omega }_n^k$，上式变为：

$$A({\omega }_n^{k+\frac{n}{2}})=A_0({\omega }_{\frac{n}{2}}^k)-{\omega }_n^k{A}_1({\omega }_{\frac{n}{2}}^k)$$

我们发现，计算 $A({\omega }_n^k)$ 和 $A({\omega }_n^{k+\frac{n}{2}})$ 所需的子问题 $A_0({\omega }_{\frac{n}{2}}^k)$ 和 $A_1({\omega }_{\frac{n}{2}}^k)$ 是完全相同的！

这意味着，一个规模为 $n$ 的问题，可以被分解为两个规模为 $\frac{n}{2}$ 的子问题，外加 $O(n)$ 的合并操作。这正是分治法的结构。其时间复杂度为：

$$T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)$$

逆变换（IFFT）

求值过程（也称为离散傅里叶变换，DFT）的逆过程——插值，可以通过逆离散傅里叶变换（IDFT）完成。可以证明，IDFT 的计算过程与 DFT 惊人地相似。

如果一个序列 $\text{sety\_0, dots, y\_{n-1}}}$ 是序列 $\text{seta\_0, dots, a\_{n-1}}}$ 的 DFT，那么：

$$a_k=\frac{1}{n}\sum _{j=0}^{n-1}{y}_j({\omega }_n^{-k}{)}^j$$

这表明，IDFT 除了主元（单位根）从 ${\omega }_n^k$ 变成了它的共轭复数 ${\omega }_n^{-k}$，并且最后结果需要除以 $n$ 之外，其余计算过程和 DFT 完全一样。因此，我们可以复用 FFT 的代码来实现 IFFT。

模板题

P3803 【模板】多项式乘法（FFT） - 洛谷

快速数论变换（NTT）

FFT 虽然快，但有一个致命弱点：浮点数精度误差。在处理系数很大或者需要取模的题目时，FFT 会因为精度问题得到错误答案。

快速数论变换（Number Theoretic Transform, NTT）是 FFT 在模数域上的变种，它使用原根替代单位根，从而在整数环内完成变换，完全避免了精度问题。

• 原根：在一个模 $p$ 的整数环中，如果一个整数 $g$ 满足 $g^k(\mathrm{mod}p)$（$k=1,\dots ,p-1$）的结果互不相同，则称 $g$ 是模 $p$ 的一个原根。
• NTT 的条件：NTT 的存在需要模数 $p$ 是一个质数，且 $p-1$ 必须是 $N$ 的倍数，其中 $N$ 是变换的长度（通常是 2 的幂）。即 $p=k\cdot N+1$ 的形式。
• NTT 中的“单位根”：我们取 $g^{(p-1)/N}(\mathrm{mod}p)$ 作为 $N$ 次“单位根” ${\omega }_N$。可以证明，它在模 $p$ 意义下拥有和复数单位根完全相同的性质，从而可以执行与 FFT 相同的分治算法。

常用的 NTT 模数：

$$\begin{gathered} 998244353=119\cdot 2^{23}+1\text{（原根为 3）}\text{ \\ 1004535809=479⋅221+1（原根为 3） \\ 469762049=7⋅226+1（原根为 3）} \end{gathered}$$

NTT 的代码实现与 FFT 非常相似，只需将复数运算替换为模意义下的整数运算即可。

生成函数

生成函数（Generating Function），又称母函数，是组合数学中一个强大的工具。它将一个无限序列 $\text{seta\_0, a\_1, a\_2, dots}}$ 与一个函数（形式幂级数）关联起来，通过对函数进行代数运算，来解决序列相关的问题（通常是计数问题）。

普通生成函数（OGF）

对于序列 $A=[a_0,a_1,a_2,\dots ]$，其普通生成函数（Ordinary Generating Function, OGF）定义为：

$$F(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$$

这里的 $x$ 是一个形式变量，我们只关心它的系数。

基本例子：

1. 序列 $[1,1,1,\dots ]$ 的 OGF 是 $F(x)=\sum _{n=0}^{\mathrm{\infty }}{x}^n=\frac{1}{1-x}$。
2. 序列 $[1,c,c^2,c^3,\dots ]$ 的 OGF 是 $F(x)=\sum _{n=0}^{\mathrm{\infty }}(cx{)}^n=\frac{1}{1-cx}$。
3. 有限序列 $[1,1,\dots ,1]$（共 $m+1$ 项）的 OGF 是 $F(x)=\sum _{n=0}^m{x}^n=\frac{1-x^{m+1}}{1-x}$。

核心思想：生成函数的强大之处在于，组合问题的“相加”和“相乘”规则，可以对应到生成函数的“相加”和“相乘”运算上。

• 加法法则：如果一个问题可以分为互斥的 A 和 B 两类，那么总方案数的生成函数等于 A 类方案的生成函数与 B 类方案的生成函数之和。
• 乘法法则：如果一个问题可以分为独立的 A 和 B 两个步骤，总方案数的生成函数等于 A 步骤方案的生成函数与 B 步骤方案的生成函数之积。

应用举例：背包问题。假设有两类物品，第一类物品的体积为 2，有无限件；第二类物品的体积为 3，有无限件。问装满容量为 $n$ 的背包有多少种方案？

• 第一类物品的生成函数（体积作为 $x$ 的指数）：$A(x)=1+x^2+x^4+\cdots =\frac{1}{1-x^2}$
• 第二类物品的生成函数：$B(x)=1+x^3+x^6+\cdots =\frac{1}{1-x^3}$

根据乘法法则，总方案的生成函数为：

$$C(x)=A(x)B(x)=\frac{1}{1-x^2}\frac{1}{1-x^3}$$

$C(x)$ 展开后 $x^n$ 的系数，就是装满容量为 $n$ 的背包的方案数。这个系数可以通过多项式求逆等操作（依赖于 NTT）来求得。

斐波那契数列的生成函数

斐波那契数列定义为 $f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}$ for $n\ge 2$。

令其生成函数为 $F(x)=\sum _{n=0}^{\mathrm{\infty }}{f}_n{x}^n$。

根据递推关系：

解出 $F(x)$:

$$F(x)(1-x-x^2)=x⟹F(x)=\frac{x}{1-x-x^2}$$

通过将这个有理分式展开成幂级数，我们可以得到斐波那契数列的通项公式。这展示了生成函数在解决递推关系上的威力。