核心概述
数论变换（NTT）：在 p=k·2^n+1 的素数模与相应原根下进行的离散傅里叶变换，用于精确的多项式卷积与点值变换，复杂度 O(n log n)。
原文引述
Description: NTT over a prime p with primitive root of order 2^n, same algorithmic pattern as FFT but with modular arithmetic. Used for exact polynomial convolution in O(n log n). Time: O(n log n) Status: tested ——摘自本节点现有英文注释
-
适用的模数与原根
- 要求模数 p 为形如 k·2^n+1 的素数，且存在 g 为 2^n 次原根。
- 常用模：
- 998244353 = 119·2^23 + 1，原根 g = 3，最大 n=23（≈8.3M 点）。
- 167772161 = 5·2^25 + 1，原根 g=3（更大多项式）。
- 469762049 = 7·2^26 + 1，原根 g=3。
- 1224736769 = 73·2^24 + 1，原根 g=3。
- 可用多模组合支持任意模（见099-数值算法-模域FFT的 CRT 合并）。
-
接口（据实现）
- void ntt(vector<uint32_t>& a, bool invert, ll mod, ll root)
- 就地做 NTT；invert 为 false 做正向，true 做逆向（需乘 inv(n)）。
- root 为当前长度的原根（实现内按层计算或预计算表）。
- vector<uint32_t> convolution_ntt(const vector<uint32_t>& A, const vector<uint32_t>& B, ll mod=998244353, ll root=3)
- 填充至 2 的幂，正向变换，点乘，逆变换，截断。
- void ntt(vector<uint32_t>& a, bool invert, ll mod, ll root)
-
核心步骤（与 FFT 同构）
- 比特反转重排 a。
- 逐层长度 len=2,4,…,n：
- wlen = root^{(p−1)/len}（正向）或其逆（逆向）。
- 对每个块 i..i+len−1，w=1：
- u = a[i + j]，v = a[i + j + len/2] * w % mod
- a[i + j] = (u + v) % mod
- a[i + j + len/2] = (u - v + mod) % mod
- w = w * wlen % mod
- 逆变换结束时，所有元素乘 inv(n) = n^{−1} mod p。
-
与其他变换的关系
- 是 FFT 在有限域的直接类比，所有 FFT 的技巧（迭代/递归、原位、预计算表）都适用。
- FWT/快速子集变换：处理按位卷积（OR/AND/XOR），而非多项式循环卷积（见 100-数值算法-快速子集变换）。
- DFT（复数）：处理实数/复系数卷积，有浮点误差（见 098-数值算法-快速傅里叶变换）。
-
输出语义
- convolution_ntt 返回 A 和 B 在模 mod 下的卷积系数（精确，无舍入误差）。
-
复杂度
- 单次 NTT O(n log n)；卷积 3 次 NTT + O(n) 乘法。
-
使用与注意
- 所有运算需在模内取模，用 094-数论-模运算、090-数论-长整型模乘。
- 模逆：inv(n) 用 powmod(n, mod−2)（mod 为素数）或 exgcd（见 091-数论-模幂、088-数论-模逆）。
- 多模扩展：若目标模不是 NTT 友好，用多模 CRT 重建（见099-数值算法-模域FFT）。
- 预计算：对同一模多次 NTT，预计算各层的根 wlen 与其逆可大幅加速。