FFT 学习笔记

FFT 学习笔记

\(\mathbf{Preview}\)

前置知识。
多项式表示法

系数表示法：就是正常的多项式表示方法。\(f(x) = \sum\limits_{i = 0}^{n - 1} a_i \times x^i\)。
点值表示法：如果我们知道 \(n\) 个数 \(b_1, \cdots, b_n\)，这些数在带入 \(f\) 多项式后他们的具体值 \(f(b_1), \cdots, f(b_n)\)，我们就可以通过这些值算出 \(f\)，因此 \(f\) 也可以用若干个点对 \(\Big(b_1, f(b_1)\Big),\cdots,\Big(b_n, f(b_n)\Big)\) 来表示。1
向量

向量是一个有方向，有长度的量，为了方便运算，起点坐标通常被设为原点。
但正如同刚才所说，向量的两个关键因素为方向和长度，所以还可以用这一种方式：

\[P = \{r, \alpha\}\]
这也被称为 极角坐标系， \(r\) 也被称为向量的模长，\(\alpha\) 自然是与 \(x\) 轴成的夹角。
向量在坐标系中大致是这样：

由于在 FFT 中不是很重要，所以粗略介绍。
弧度制

一个点在一个以原点为中心半径为 \(1\) 的圆上时，这个点与 \(x\) 轴的夹角在弧度制下被表示为这个点到圆与 \(x\) 轴的交点的圆弧长度。简单来说，\(2\pi = 360\degree\)。

<img alt="image-20250726110950605" >

复数

设 \(a,b\) 为实数，\(i^2 = -1\)，则形如 \(a+bi\) 的数被称为复数。
在复平面中，\(x\) 轴表示实数，\(y\) 轴（除原点）表示虚数，从 \((0, 0)\to (a, b)\) 的向量表示 \(a+bi\)。
模长：表示 \(a+bi\) 向量的模长，即 \(\sqrt{a^2 + b^2}\)。
幅角：以逆时针为正方向，\(x\) 轴正方向到 \(a+bi\) 的向量形成的有向角。
加法运算：\((a+bi)+(c+di) = (a+c)+(b+d)i\)
减法运算：\((a+bi)-(c+di) = (a-c)+(b-d)i\)
乘法运算：

• 几何定义：复数相乘，模长相乘，幅角相加
  
• 代数定义：\((a+bi)\times (c+di) = (ac - bd) + (bc + ad)i\)。
  

除法定义在本文中不提及。
单位根

下文中，默认 \(n\) 为 \(2\) 的正整数次幂
以单位圆原点为起点，圆的 \(n\) 等分点为终点，做 \(n\) 个向量，设幅角为正且最小的向量对应的复数为 \(w_n\)，称为 \(n\) 次单位根。

<img alt="image-20250726112629884" >

根据复数乘法的运算法则，其余 \(n - 1\) 个复数为 \(w_n^2, w_n^3,\cdots,w_n^{n}\)
注意 \(w_n^0 = w_n^n\)（对应复平面上以 \(x\) 轴为正方向的向量，就是图中的 \(u\)）
由欧拉公式，\(w_n^k = \cos k\dfrac{2\pi}{n}+i\sin{k\dfrac{2\pi}{n}}\)，且有 \(w_{2n}^{2k} = w_n^k,w_{n}^{k+\frac{n}{2}}=-w_{n}^k,w_n^0 = w_n^n = 1\)。
接下来进入正题。
\(\mathbf{Part. 0 \ \ 思路}\)

首先，我们考虑如何计算两个多项式 \(P, Q\) 的乘法，假设次数分别为 \(n - 1, m - 1\)，为了方便后面的分治，我们先把 \(P, Q\) 的长度扩成一个大于 \(n + m\) 的 \(2\) 的幂次。设这个幂次为 \(l = 2^t\)。
显然，在系数表示法中，我们只能 \(\mathcal{O}(n^2)\) 求乘法。
但是，如果我们能把 \(P, Q\) 都转化成点值表示法，其中 \(P\) 的点值表示法为 \(\Big(x_1, P(x_1)\Big),\cdots,\Big(x_l, P(x_l)\Big)\)，\(Q\) 的点值表示法为 \(\Big(x_1, Q(x_1)\Big),\cdots,\Big(x_l, Q(x_l)\Big)\)。然后，因为 \(P(x_i)\) 和 \(Q(x_i)\) 是两个多项式的结果，所以我们可以直接对每个 \(P(x_i) \times Q(x_i) = Z(x_i)\)。对于 \(\Big(x_1, Z(x_1)\Big),\cdots,\Big(x_l, Z(x_l)\Big)\)，我们将点值表示法转化回系数表示法，就能得到 \(P \times Q\) 的值。
整合思路，我们需要将系数表示法转化为点值表示法，再将点值表示法转化回系数表示法。
第一步被称为 \(\mathbf{FFT}\)，第二部被称为 \(\mathbf{IFFT}\)。
\(\mathbf{Part. 1 \ \ FFT}\)

\(\mathbf{FFT}\) 是为了解决如何快速将一个多项式从系数表示法转化为多项式表示法的。如果我们直接暴力计算，我们要对于 \(n\) 个数，每个数计算 \(f(x)\)，总复杂度 \(\mathcal{O}(n^2)\)。（相关章节：\(\mathbf{Preview}，多项式表示法\)）
设我们现在想把 \(A(x) = \sum\limits_{i = 0}^{n - 1} a_i\times x^i\) 转化为点值表示法。
在 \(\mathbf{Preview}\) 中的 多项式表示法 中，由 ，我们知道一个多项式可以被 \(n\) 个点唯一确定。
假设最终的点值表示法是 \(\Big(x_1, f(x_1)\Big),\cdots,\Big(x_n, f(x_n)\Big)\)，我们考虑将 \(x_1, \cdots, x_n\) 设为 \(w_n^0, \cdots, w_n^{n - 1}\)，然后计算 \(f(w_n^0),\cdots,f(w_n^{n - 1})\)。所以我们只需要计算 \(A(w_n^0),\cdots,A(w_n^{n - 1})\)。2
考虑分治计算这个值。我们把 \(A(x)\) 按照下标奇偶性进行分类：

\[\begin{aligned}A(x) = & (a_0 + a_2 \times x^2 + \cdots + a_{n - 2} \times x^{n-2}) +\\& (a_1 \times x^1 + a_3\times x^3 + \cdots + a_{n - 1}\times x^{n - 1})\end{aligned}\]
然后继续考虑构造 \(A_1, A_2\)：

\[A_1(x) = a_0 + a_2 \times x + \cdots + a_{n - 2}\times x^{\frac{n}{2} - 1}\\A_2(x) = a_1 + a_3 \times x + \cdots + a_{n - 1} \times x ^ {\frac{n}{2} - 1}\]
那么综合 \((2)(3)\)：

\[A(x) = A_1(x^2) + xA_2(x^2)\]
由  知，我们需要把 \(w_n^k\) 代入多项式。
由于我们需要分治，考虑将 \(k\) 按照 \(k < \dfrac{n}{2}\) 和 \(k \geq \dfrac{n}{2}\) 考虑。
对于 \(k < \dfrac{n}{2}\)：（接下来的化简如果不懂，可以尝试结合 \(\mathbf{Preview}\) 中的 单位根 来看）

\[\begin{aligned}A(w_n^k) & = A_1(w_n^{2k}) + w_n^kA_2(w_n^{2k})\\& = A_1(w_{\frac{n}{2}}^k) + w_n^kA_2(w_{\frac{n}{2}}^k)\end{aligned}\]
对于 \(k\geq \dfrac{n}{2}\)，考虑 \(k = k' + \dfrac{n}{2}\)：

\[\begin{aligned}A(w_n^{k}) & = A_1(w_n^{2k' + n}) + w_n^{k' + \frac{n}{2}} A_2(w_{n}^{2k' + n})\\& = A_1(w_n^{2k'} \times w_n^n) + w_n^{k'} w_n^{\frac{n}{2}} A_2(w_n^{2k'} \times w_n^n)\\& = A_1(w_n^{2k'}) - w_n^{k'} A_2(w_n^{2k'})\\& = A_1(w_{\frac{n}{2}}^{k'}) - w_n^{k'} A_2(w_{\frac{n}{2}}^{k'})\end{aligned}\]
我们发现，对于 \((5)\) 和 \((6)\) 的结果式，它们再 \(A_1\) 和 \(A_2\) 多项式中代入得值是一样的（都是 \(w_{\frac{n}{2}}^k\)，其中 \(k < \frac{n}{2}\)）。因此，如果我们分治求出来了 \(A_1(w_{\frac{n}{2}}^{k})\) 和 \(A_2(w_{\frac{n}{2}}^k)\)，我们就可以通过 \((5)(6)\) 来算出来 \(k < \dfrac{n}{2}, A(w_n^k)\) 和 \(k \geq \dfrac{n}{2},A(w_n^{k})\)，因此拼起来就是完整的 \(A(w_n^k)\)。
因此，我们只需要分治求出来 \(A_1(w_{\frac{n}{2}}^{k})\) 和 \(A_2(w_{\frac{n}{2}}^k)\)，然后求出来 \(A(w_n^k)\)，我们就可以得出 \(A\) 的点值表示法。对于每一层，我们只需要 \(\mathcal{O}(n)\) 的时间复杂度计算，总共 \(\mathcal{O}(\log n)\) 层，因此时间复杂度为 \(\mathcal{O}(n\log n)\)。
\(\mathbf{Part. 2 \ \ IFFT}\)

\(\mathbf{IFFT}\) 是为了解决如何快速将一个多项式从点值表示法转化为系数表示法的。（相关章节：\(\mathbf{Preview}，多项式表示法\)）
假设我们对于多项式 \(A(x) = \sum\limits_{i = 0}^{n - 1} a_i \times x^i\)，求出来了 \(A\) 的点值表示 \(\Big(w_n^0, t_0\Big), \cdots, \Big(w_n^{n - 1}, t_{n - 1}\Big)\)，则我们想要通过 \(t\) 数组来还原出 \(a\) 数组。
我们考虑构造数组 \(c\)，使得 \(c_k = \sum\limits_{i = 0}^{n - 1} t_i \times(w_n^{-k})^i\)。这个式子的含义是，我们考虑对于 \(f(x) = \sum\limits_{i = 0}^{n - 1}t_i \times x ^ i\) 这个多项式，代入 \((w_n^0, \cdots, w_n^{-(n - 1)})\) 计算 \(f(x)\)（也就是 \(t\) 数组）的点值表示法，得到 \(c_0, \cdots, c_{n - 1}\)。3

这里你可以这样理解：我们在对 \(A\) 求出代入 \((w_n^0, \cdots, w_n^{n - 1})\) 时的点值表示时，再对这个结果代入 \((w_n^0, \cdots, w_n^{-(n - 1)})\) 时求出点值表示，最后得到 \(c\) 数组。

考虑对这个 \(c\) 数组进行变换：

\[\begin{aligned}c_k & = \sum_{i = 0}^{n - 1} t_i \times(w_n^{-k})^i\\& = \sum_{i = 0}^{n - 1} \color{red}A(w_n^{i})\color{black}\times (w_n^{-k})^i\\& = \sum_{i = 0}^{n - 1} \color{red}\sum_{j = 0}^{n - 1} a_j \times (w_n^i)^j\color{black}\times (w_n^{-k})^i\\& = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}a_j \times (w_n\color{red}^j\color{black})\color{red}^i\color{black} \times (w_n^{-k})^i\\& = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}a_j \times \color{red}(\color{black}w_n^j\times w_n^{-k}\color{red})^i\color{black}\\& = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}a_j \times (\color{red}w_n^{j - k}\color{black})^i\\& = \color{red}\sum_{j = 0}^{n - 1}a_j \times \sum_{i = 0}^{n - 1}\color{black}(w_n^{j - k})^i\end{aligned}\]
我们考虑 \(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i\) 如何快速计算。容易发现这是一个等比数列的形式，则：

• \(j - k = 0\)，则 \(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i = \sum\limits_{i = 0}^{n - 1}1^i = n\)。
  
• \(j = k \neq 0\)，则由于等比数列的比为 \(w_{n}^{j - k}\)，则 \(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i = \dfrac{(w_n^{j - k})^n - (w_n^{j - k})^0}{w_{n}^{j - k} - 1} = 0\)。
  

因此，我们发现，只有当 \(j = k\) 时，\(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i\) 为 \(n\)，其余情况均为 \(0\)。因此，\((21)\) 结果式转化为：

\[c_k = \sum_{j = 0}^{n - 1}a_j \times \sum_{i = 0}^{n - 1}(w_n^{j - k})^i = a_k \times n\]
因此，\(a_k = c_k \times \dfrac{1}{n}\)，而 \(a_k\) 就是我们想求的值！
考虑 \(c_k\) 是什么，由 ，我们知道 \(c_k\) 是对于 \(f(x) = \sum\limits_{i = 0}^{n - 1}t_i \times x ^ i\) 这个多项式，代入 \((w_n^0, \cdots, w_n^{-(n - 1)})\) 计算 \(f(x)\)（也就是 \(t\) 数组）的点值表示法。因此，我们只需要对 \(t_0, \cdots, t_{n - 1}\) 求出来点值表示即可，这个和上面 \(\mathbf{Part. 1 \ \ FFT}\) 唯一的不同就是代入值中单位根的次数一个为正，一个为负。
所以，\(\mathbf{IFFT}\) 实际上就是对 \(t\) 数组再做一遍 \(\mathbf{FFT}\)，然后对于每个 \(c_k\) 乘上 \(\dfrac{1}{n}\) 就是 \(a_k\)。
\(\mathbf{Part. +\infin \ \ Details}\)

[code]/*******************************| Author:  DE_aemmprty| Problem: P3803 【模板】多项式乘法（FFT）| Contest: Luogu| URL:     https://www.luogu.com.cn/problem/P3803| When:    2025-07-26 15:03:20| | Memory:  500 MB| Time:    2000 ms*******************************/#include using namespace std;int read() {    char c = getchar(); int x = 0;    while ((c < '0' || c > '9') && c != '-') c = getchar();    while (c >= '0' && c