什么是 NTT

NTT，全称是 Number Theoretic Transform，中文通常叫“数论变换”。

它可以理解为：

在模意义下进行的 FFT，用来快速计算多项式乘法，也就是卷积。

普通的多项式乘法是 $O(n^2)$ 的，而 NTT 可以把复杂度降到 $O(n\log n)$。

NTT 解决什么问题

假设有两个多项式：

$$A(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}$$ $$B(x)=b_0+b_1x+b_2x^2+\cdots+b_{m-1}x^{m-1}$$

它们的乘积为：

$$C(x)=A(x)B(x)$$

其中 $C$ 的第 $k$ 项系数是：

$$c_k=\sum_{i+j=k}a_i b_j$$

这就是卷积。

如果直接枚举 $i,j$，复杂度是 $O(nm)$。当 $n,m$ 很大时会很慢。

NTT 的作用就是快速求出所有 $c_k$。

NTT 和 FFT 的关系

FFT 是快速傅里叶变换，它利用复数单位根来加速多项式乘法。

NTT 的思想和 FFT 很像，但它不使用复数，而是在模意义下使用“原根”构造出来的单位根。

可以粗略理解为：

• FFT：在复数域里做快速变换；
• NTT：在模质数意义下做快速变换。

NTT 的好处是没有浮点误差，结果天然是整数取模后的结果。

为什么需要特殊的模数

NTT 不能随便选模数。

为了能做长度为 $n$ 的 NTT，通常需要模数 $p$ 满足：

$$p = c \cdot 2^k + 1$$

这样模 $p$ 意义下才容易找到足够多的 $2^k$ 次单位根。

竞赛中最常用的模数是：

$$998244353 = 119 \cdot 2^{23} + 1$$

它的原根通常取：

$$g = 3$$

所以 $998244353$ 非常适合做 NTT，最大可以支持长度不超过 $2^{23}$ 的变换。

NTT 的核心思想

多项式有两种表示方式。

第一种是系数表示：

$$A(x)=a_0+a_1x+a_2x^2+\cdots$$

第二种是点值表示：

$$(x_0,A(x_0)),(x_1,A(x_1)),\ldots$$

如果两个多项式都变成点值表示，那么乘法非常简单。

因为：

$$C(x_i)=A(x_i)B(x_i)$$

也就是说，每个点对应的值直接相乘即可。

所以多项式乘法可以分成三步：

1. 把 $A$ 和 $B$ 从系数表示变成点值表示；
2. 对每个位置做乘法；
3. 再把结果从点值表示变回系数表示。

NTT 做的就是第 $1$ 步和第 $3$ 步。

NTT 的大致流程

设需要计算的长度为 $len$，其中 $len$ 是 $2$ 的幂，并且要满足：

$$len \ge n+m-1$$

流程如下：

1. 把两个多项式的系数数组补零到长度 $len$；
2. 对数组 $A$ 做 NTT；
3. 对数组 $B$ 做 NTT；
4. 每一项相乘，得到点值形式的 $C$；
5. 对 $C$ 做逆 NTT；
6. 得到答案系数。

复杂度是：

$$O(len\log len)$$

正变换和逆变换

NTT 有两个方向。

正变换把系数变成点值，逆变换把点值变回系数。

正变换使用单位根 $w$，逆变换使用 $w$ 的逆元。

最后逆变换结束后，还要把每一项乘上 $len$ 的逆元。

也就是：

$$a_i \leftarrow a_i \cdot len^{-1}$$

这一步非常重要，否则答案会整体多乘一个 $len$。

为什么 NTT 可以做到 $O(n\log n)$

NTT 和 FFT 一样，使用分治思想。

一个多项式可以按照下标奇偶拆成两部分：

$$A(x)=A_0(x^2)+xA_1(x^2)$$

其中：

• $A_0$ 是偶数下标项组成的多项式；
• $A_1$ 是奇数下标项组成的多项式。

通过单位根的性质，可以把长度为 $n$ 的问题拆成两个长度为 $n/2$ 的问题。

所以复杂度满足：

$$T(n)=2T\left(\frac n2\right)+O(n)$$

因此总复杂度为：

$$O(n\log n)$$

NTT 常见用途

NTT 最常见的用途是快速卷积。

也就是快速计算：

$$c_k=\sum_{i+j=k}a_i b_j$$

它经常出现在这些问题里：

• 多项式乘法；
• 生成函数；
• 组合计数；
• 分治优化卷积；
• 多项式求逆、开根、取对数、指数；
• 大整数乘法的取模版本。

和普通卷积的区别

普通卷积直接枚举每一对 $i,j$：

$$c_{i+j} \mathrel{+}= a_i b_j$$

复杂度是 $O(n^2)$。

NTT 通过变换后逐项相乘，把复杂度降到 $O(n\log n)$。

所以当数据规模很大，比如 $n$ 达到 $10^5$ 或更大时，NTT 就非常有用。

一句话总结

NTT 是一种在模质数意义下进行的快速变换，可以把多项式乘法，也就是卷积，从 $O(n^2)$ 优化到 $O(n\log n)$。

它本质上是 FFT 在整数取模环境下的版本，常用于生成函数和多项式相关题目。