先放大佬博客，读者可以无视我的拙劣笔记

1. FFT学习笔记
2. NTT与多项式全家桶
3. 多项式计数杂谈

多项式的定义与性质

环和域

简单地说，定义了具有通常性质的加法、减法、乘法和除法，且关于这些运算封闭的集合称为域。域是特殊的环。

• 有理数集 $\mathbb{Q}$、实数集 $\mathbb{R}$ 和 复数集 $\mathbb{C}$ 都是域。整数集 $\mathbb{Z}$ 是一个环，但不是一个域，因为整数集关于除法不封闭。
• $\color{blue}{设\, p \, 是一个质数，那么模 \, p \, 意义下的集合 \{0,1,\cdots,p-1\} 是一个域，记为 \mathbb{F}_p}$。

多项式

设 $\mathcal{R}$ 是一个环，$a_0, a_1, \cdots, a_n$ 为 $\mathcal{R}$ 中的元素且 $a_n \neq 0$，$x^0$ 始终表示 $1$，则

$$ f(x) = \sum_{k = 0}^n a_k x^k $$

称为 $\mathcal{R}$ 上次数为 $n$ 的多项式。
此后涉及的所有多项式均认为是某个域上的多项式。

卷积

对于数组 $a, b$，令

$$ c_k = \sum_{i + j = k} a_ib_j = \sum_{i = 0}^k a_ib_{k - i} = \sum_{j = 0}^k a_{k - j}b_j $$

则称 $c$ 为 $a$ 和 $b$ 的卷积。

多项式乘法

设 $\displaystyle f(x) = \sum_{k = 0}^n a_kx^k$，$\displaystyle g(x) = \sum_{k = 0}^m b_kx^k$，利用分配律可得

$$ f(x)g(x) = \sum_{k = 0}^{n + m} c_kx^k $$

其中 $c$ 为 $a$ 和 $b$ 的卷积。
显然，直接计算的时间复杂度为 $\Theta(nm)$。

多项式的点值表示

设 $\displaystyle f(x) = \sum_{k = 0}^n a_kx^k$ 为次数不大于 $n$ 的多项式，对于 $n + 1$ 个点 $x_0, x_1, \cdots, x_n$，有

$$ \left(\begin{array}{c} f\left(x_{0}\right) \\\ f\left(x_{1}\right) \\\ f\left(x_{2}\right) \\\ \vdots \\\ f\left(x_{x_{n}}\right) \end{array}\right)=\left(\begin{array}{ccccc} 1 & x_{0} & x_{0}^{2} & \cdots & x_{0}^{n} \\\ 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{n} \\\ 1 & x_{2} & x_{2}^{2} & \cdots & x_{2}^{n} \\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ 1 & x_{n} & x_{n}^{2} & \cdots & x_{n}^{n} \end{array}\right)\left(\begin{array}{c} a_{0} \\\ a_{1} \\\ a_{2} \\\ \vdots \\\ a_{n} \end{array}\right) $$

若 $x_0, x_1, \cdots, x_n$ 互不相同，则等式右边的矩阵可逆，那么

$$ \left(\begin{array}{c} a_{0} \\\ a_{1} \\\ a_{2} \\\ \vdots \\\ a_{n} \end{array}\right)=\left(\begin{array}{ccccc} 1 & x_{0} & x_{0}^{2} & \cdots & x_{0}^{n} \\\ 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{n} \\\ 1 & x_{2} & x_{2}^{2} & \cdots & x_{2}^{n} \\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ 1 & x_{n} & x_{n}^{2} & \cdots & x_{n}^{n} \end{array}\right)^{-1}\left(\begin{array}{c} f\left(x_{0}\right) \\\ f\left(x_{1}\right) \\\ f\left(x_{2}\right) \\\ \vdots \\\ f\left(x_{x_{n}}\right) \end{array}\right) $$

$\color{red}{即 \, n + 1 \, 个点值对 (x_k, f(x_k)) 可以唯一确定 f(x)}$。

设 $f(x), g(x)$ 为次数分别为 $n, m$ 的多项式，有 $n + m + 1$ 个互不相同的点 $x_0, x_1, \cdots, x_{n + m}$。

$\color{red}{若已知所有的 f(x_k) 和 g(x_k)，则只要以 \Theta(n + m) 的时间复杂度计算所有的 f(x_k)g(x_k)，就可以唯一确定\\\ f(x)g(x)}。$

当然，对于 $f(x) + g(x)$ 也是类似的。

多项式的根

设 $F, K$ 是域且 $F \subseteq K$，$f(x)$ 是 $F(x)$ 上的多项式，$\alpha$ 是 $K$ 中的元素。若 $f(\alpha) = 0$，则称 $\alpha$ 为 $f(x)$ 的一个根。

$\color{blue}{f(x) 的根不一定在 \, F \, 中。}$ 例如 $f(x) = x^2 - 2$ 是 $\mathbb{Q}$ 上的多项式，$\sqrt{2}$ 是 $f(x)$ 的一个根，但 $\sqrt{2}$ 不在 $\mathbb{Q}$ 中。

单位根

多项式 $x^n - 1$ 根称为 $n$ 次单位根。

• 设 $\omega = e^{\frac{2\pi i}{n}}$ 为复数，由欧拉公式

$$ e^{ix} = \cos x + i\sin x $$

容易验证 $\omega_n^n = 1$；

• 对于质数 $p = kn + 1$，设 $\omega_n = g^{\frac{p-1}{n}}$ 为 $\mathbb{F}_p$ 中的元素，其中 $g$ 为模 $p$ 的原根，那么显然 $\omega_n^n = 1$。

在上述的两种情况下，$1, \omega_n, \omega_n^2, \cdots, \omega_n^{n - 1}$ 为 $n$ 个互不相同的 $n$ 次单位根。

FFT 的原理

DFT 的引入

DFT 的定义

设 $a$ 为大小为 $n$ 的数组，$\displaystyle f(x)=\sum_{k = 0}^{n - 1} a_kx^k$，定义

$$ {\rm DFT}(a) = (f(1), f(\omega_n), f(\omega_n^2), \cdots, f(\omega_n^{n - 1})) $$

称为 $a$ 的离散傅里叶变换，或 $a$ 的 $\color{purple}{\rm DFT}$。

$\color{red}{也就是说，{\rm DFT} 将 f(x) 的系数数组 a 变换成 f(x) 在每个 \omega_n^k 处的值，从而得到 f(x) 的一个点值表示}。$

DFT 的逆变换

$\rm DFT$ 的逆变换称为 $\rm IDFT$，也记作 $\color{purple}{\rm DFT^{-1}}$。$\rm IDFT$ 将 $f(x)$ 在 $n$ 个 $n$ 次单位根处的点值表示变换为其系数表示。

$\color{red}{容易证明，只要将 {\rm DFT} 中的 \omega_n 换成 \omega_n^{-1} 并将结果除以 n，就可以得到 {\rm IDFT}}$。

更形式化地说，设 $\displaystyle g(x) = \sum_{k = 0}^{n - 1} f(\omega_n^k)x^k$，则有

$$ \begin{aligned} a &= {\rm DFT}^{-1} ({\rm DFT}(a)) \\\ &= \frac{1}{n}(g(1),g(\omega_n^{-1}),g(\omega_n^{-2}),\cdots,g(\omega_n^{-(n - 1)})) \end{aligned} $$

循环卷积

对于大小为 $n$ 的数组 $a,b$，令

$$ c_k = \sum_{(i + j) \mod n = k}a_ib_j = \sum_{i + j = k}a_ib_j + \sum_{i + j = n + k}a_ib_j $$

则称 $c$ 为 $a$ 和 $b$ 的循环卷积，用 $a \otimes b$ 表示。

卷积定理

设 $\displaystyle f(x) = \sum_{k = 0}^{n - 1}a_kx^k$，$\displaystyle g(x) = \sum_{k = 0}^{n - 1}b_kx^k$，$\displaystyle h(x) = \sum_{k = 0}^{n - 1}c_kx^k$。对于任意整数 $s$，由于 $(\omega_n^s)^n = 1$，有

$$ \begin{aligned} f(\omega_n^s)g(\omega_n^s) &= \sum_{k = 0}^{n - 1}\left(\sum_{i + j = k}a_ib_j + \sum_{i + j = n + k}a_ib_j\right)(\omega_n^s)^k \\\ &= h(\omega_n^s) \end{aligned} $$

由于 $h(x)$ 是次数不大于 $n - 1$ 的多项式，由点值表示的唯一性得

$$ {\rm DFT}^{-1}({\rm DFT}(a) \circ {\rm DFT}(b)) = a \otimes b $$

其中 $\circ$ 为逐元素相乘的运算。

$\color{red}{由此可知，可以利用 {\rm DFT} 计算循环卷积}。$
$\color{red}{特别地，若 \, f(x)g(x) \, 的次数不大于 \, n - 1 \, ，则 \, h(x) = f(x)g(x) \, ，此时相当于用循环卷积计算普通卷积。}$

注记

狭义的 $\rm DFT$ 仅指代复数域上的 $\rm DFT$，因此常把 $\mathbb{F}_p$ 上的 $\rm DFT$ 称为数论变换，或 $\rm NTT$。当然，这两种形式的 $\rm DFT$ 的原理是相同的。

DFT 的快速计算

FFT 综述

快速傅里叶变换，或 $\rm FFT$，是快速计算 $\rm DFT$ 的方法，其时间复杂度仅为 $O(n\log n)$。

在 $\rm OI$ 中，通常只实现要求 $n$ 为 $2$ 的幂的 $\rm FFT$。如果要计算 $a$ 和 $b$ 的卷积 $c$，可以取 $n$ 为不小于 $c$ 的大小的最小的 $2$ 的幂，将 $a$ 和 $b$ 的大小均扩充为 $n$ 后再计算。如果要计算循环卷积，可以先计算普通卷积，再将第 $k + n$ 项加到第 $k$ 项上。

对于模一个质数 $p$ 的情况，若 $p = k \cdot 2^l + 1$，那么若 $n$ 为 $2$ 的幂且不大于 $2^l$，则 $n$ 次单位根在 $\mathbb{F}_p$ 中，从而可以计算 $\rm DFT$，并且可以用要求 $n$ 为 $2$ 的幂的 $\rm FFT$ 计算。

• 一个常见的 $p$ 是

$$998244353 = 7 \times 17 \times 2^{23} + 1$$

相应的原根可取 $3$。$\color{blue}{注意 \, 2^{23} < 10^7。}$

FFT 的实现

设 $n$ 为 $2$ 的幂。对于 $\displaystyle f(x) = \sum_{k = 0}^{n - 1}a_kx^k$，设

$$ \begin{aligned} f_0(x) &= \sum_{k = 0}^{\frac{n}{2} - 1} a_{2k}x^k \\\ f_1(x) &= \sum_{k = 0}^{\frac{n}{2} - 1} a_{2k+1}x^k \end{aligned} $$

那么有 $f(x) = f_0(x^2) + xf_1(x^2)$。

对于任意整数 $s$，有 $(\omega_n^s)^2 = \omega_{\frac{n}{2}}^s$。当 $0 \leqslant s < \frac{n}{2}$，有

$$ f(\omega_n^s) = f_0(\omega_{\frac{n}{2}}^s) + \omega_n^{s}f_1(\omega_{\frac{n}{2}}^s) $$

注意到 $\omega_n^{\frac{n}{2}} = -1$，当 $\frac{n}{2} \leqslant s < n$ 时，有

$$ f(\omega_n^s) = f_0(\omega_{\frac{n}{2}}^{s - \frac{n}{2}}) - \omega_n^{s - \frac{n}{2}}f_1(\omega_{\frac{n}{2}}^{s - \frac{n}{2}}) $$

那么只要递归地计算出 $f_0(x)$ 和 $f_1(x)$ 的 $\rm DFT$，就可以以 $\Theta(n)$ 的时间复杂度计算 $f(x)$ 的 $\rm DFT$，总时间复杂度为 $\Theta(n\log n)$。

对于 $n = 2^k$，可以 将所有下标视为 $k$ 位二进制数。将下标根据是否小于 $\frac{n}{2}$ 划分成两部分是根据最高位进行划分，而根据奇偶性划分成两部分是根据最低位进行划分。对于前者，可以自然地将递归树展开。而对于后者，只要将所有下标的二进制位翻转，就可以转化为前者的情况。

$\color{blue}{展开递归树不仅会减少递归的开销，还会去除冗余的操作，并且优化了内存访问效率。因此，非递归实现的\\\ 效率高的多，几乎没有写递归的实现。}$

$\color{blue}{这一部分的数学推导和展开递归树的方法如果没有搞清楚，也可以直接记住具体的代码实现。}$

详细讨论 DFT

• $A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n - 1}x^{n - 1}$，其中$n = 2^b$。
• $A_0(x) = a_0 + a_2x + \cdots + a_{n - 2}x^{\frac{n - 2}{2}}$
• $A_1(x) = a_1 + a_3x^2 + \cdots + a_{n - 1}x^{\frac{n - 2}{2}}$
• $A(x) = A_0(x^2) + xA_1(x^2)$
• 当 $0 \leqslant k \leqslant \frac{n}{2} - 1$，$A(\omega_n^k) = A_0((\omega_n^k)^2) + \omega_n^k \cdot A_1((\omega_n^k)^2)$
• 得到 $A(\omega_n^k) = A_0(\omega_{\frac{n}{2}}^k) + \omega_n^k A_1(\omega_{\frac{n}{2}}^k)$
• 那么 $\frac{n}{2} \leqslant k + \frac{n}{2} \leqslant n - 1$，$A(\omega_n^{k + \frac{n}{2}}) = A_0((\omega_n^{k + \frac{n}{2}})^2) + \omega_n^{k + \frac{n}{2}} \cdot A_1((\omega_n^{k + \frac{n}{2}})^2)$
• 得到 $A(\omega_n^{k + \frac{n}{2}}) = A_0(\omega_{\frac{n}{2}}^k) - \omega_n^k \cdot A_1(\omega_{\frac{n}{2}}^k)$
• 我们可以发现，这东西完全 可以递归算，$T(n) = 2T(\frac{n}{2}) + O(n) = O(n\log n)$

详细讨论 IDFT

• 将 $\rm DFT$ 得到的点值转换为系数，这一过程就叫做 $\color{purple}{\rm IDFT}$
• 假如我们得到了 $A(x)$ 的点值，设其为 $(d_0, d_1, \cdots, d_{n - 1})$，构造一个多项式 $F(x) = (d_0, d_1, d_{n - 1})$
• 设 $c(k)$ 为 $x = \omega_n^{-k}$ 时的点值
  $$ \begin{aligned} c_k &= \sum_{i = 0}^{n - 1}d_i \cdot (\omega_n^{-k})^i = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}a_j \cdot (\omega_n^i)^j \cdot (\omega_n^{-k})^i = \sum_{j = 0}^{n - 1} a_j \sum_{i = 0}^{n - 1}(\omega_n^{j - k})^i \\\ &= \sum_{j = 0}^{n - 1} a_j \cdot n \cdot [j = k] = n \cdot a_k \end{aligned} $$

注记

虽然 $\rm NTT$ 指的是 $\rm \mathbb{F}_p$ 上的 $\rm DFT$，而不是计算这个 $\rm DFT$ 的 $\rm FFT$ 方法，但习惯上也将后者称为 $\rm NTT$。

• 对于结果模 $p$ 的问题，只能使用 $\rm NTT$。
• 对于涉及浮点数计算的问题，只能使用复数 $\rm DFT$。
• 对于只涉及整数计算，且结果不太大的问题，两种形式的 $\rm DFT$ 都可以考虑，需要综合考虑结果的大小和特定环境的运行效率来决定选用哪一种。

FFT 模板

const int N = 300010;
const double PI = acos(-1);

int n, m;
struct Complex {
    double x, y;
    Complex operator+ (const Complex& t) const {
        return {x + t.x, y + t.y}; 
    }
    Complex operator- (const Complex& t) const {
        return {x - t.x, y - t.y};
    }
    Complex operator* (const Complex& t) const {
        return {x * t.x - y * t.y, x * t.y + y * t.x}; 
    }
} a[N], b[N];  

int rev[N], bit, tot; // rev表示翻转之后的结果，bit表示总位数，tot表示总长度 

void fft(Complex a[], int inv) {
    for (int i = 0; i < tot; ++i) {
        if (i < rev[i]) std::swap(a[i], a[rev[i]]);
    }
    for (int mid = 1; mid < tot; mid <<= 1) {
        auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
        for (int i = 0; i < tot; i += mid * 2) {
            auto wk = Complex({1, 0});
            for (int j = 0; j < mid; ++j, wk = wk * w1) {
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y, a[i + j + mid] = x - y;
            }
        } 
    }
}

FFT 的应用

FFT 的基本应用

解决能转化为计算卷积的问题：

• 直接的计算；
• 多项式的运算；
• 字符串匹配。

直接的计算

一些问题经过简单的推导即可推出可以用计算卷积来解决，这类问题多形如对所有不大于 $n$ 的 $k$ 求出某个东西，其中 $k$ 的答案为求某个卷积后结果数组的第 $k$ 项。

一些练习题

1. 【模板】多项式乘法（FFT）
2. Nikita and Order Statistics
3. 礼物
4. 序列计数
5. 高速フーリエ変換
6. Convolution