分类 / 信息学竞赛（OI）
首次发表于 2021-07-16 · 上次修改于 2023-10-17 · 分类：信息学竞赛（OI）
2021 TPC 腾讯程序设计竞赛 第一季
首次发表于 2021-07-16 · 上次修改于 2025-09-02 · 分类：信息学竞赛（OI）
快速数论变换（NTT）
将快速傅里叶变换（FFT）中的单位根换成原根，就成了快速数论变换（NTT）。NTT 没有精度误差，但是 NTT 要求系数为整数，且要对特殊的质数取模（设这个质数是 $p$，且 $p=r \times 2^k+1$，$2 \not | r$，$k \in \mathbb{N}$，那么它只能用来处理乘积的最高次数 $<2^k$ 的多项式乘法）。
（第 3 页，共 5 页）