模域FFT（NTT，Number Theoretic Transform）：在模素数 p 的有限域上，以原根的 n 次单位根为基础实现“离散傅里叶变换”用于多项式卷积，复杂度 O(n log n)。常用 p=998244353，原根 g=3，支持 n 为 2 的幂。
Description: Iterative NTT under a suitable prime modulus p with primitive root g. Supports convolution by forward NTT, pointwise multiply, and inverse NTT with inv(n). Time: O(n log n) Status: tested
-
选择模数与原根
- 需 p 为形如 k·2^L + 1 的素数，存在 2^L 阶原根。
- 常用：p = 998244353 = 119·2^23 + 1，原根 g = 3，支持最大 n ≤ 2^23。
- 若需更大 n，可切换更大模数或多模 CRT 合并（见下）。
-
接口（据实现）
- void ntt(vector<uint32_t>& a, bool invert)
- 长度 n 为 2 的幂；invert=false 正变换，true 逆变换（末尾乘 inv(n)）。
- 预计算根 wlen = g^{(p−1)/len}（逆变换用其逆）与比特反转重排。
- vector<uint32_t> convolution_mod(const vector<uint32_t>& A, const vector<uint32_t>& B, uint32_t p=998244353, uint32_t g=3)
- 执行两次正变换与一次逆变换，返回模 p 下的卷积。
- 可选：多模卷积 convolution_anymod(A,B)：
- 在多个 NTT 友好模 p_i 上分别卷积，再用 081-数论-中国剩余定理 合并到目标模或 64 位整数（参见“CRT 合并”）。
- void ntt(vector<uint32_t>& a, bool invert)
-
核心算法（迭代 Cooley–Tukey）
- 比特反转重排 a。
- 逐层长度 len=2,4,…,n：
- 取 wlen = g^{(p−1)/len}（逆变换取其逆元）。
- 对每个块 j..j+len-1，w=1：
- 对 i=j..j+len/2−1：
- u=a[i]，v=a[i+len/2]*w mod p
- a[i]=(u+v) mod p；a[i+len/2]=(u−v+p) mod p
- w=w*wlen mod p
- 对 i=j..j+len/2−1：
- 逆变换结束后，乘 inv_n = n^{−1} mod p（见 088-数论-模逆）。
-
卷积流程
- 置 n 为不小于 |A|+|B|−1 的最小 2 的幂，填零扩展到 n。
- NTT(A)、NTT(B)，逐点相乘 C[i]=A[i]*B[i] mod p，逆 NTT(C)。
- 截断到长度 |A|+|B|−1。
-
CRT 合并（任意模/大数精确卷积）
- 选若干互素 NTT 模 p1,p2,p3（如 167772161, 469762049, 1224736769）。
- 分别计算 C_k(i)；令 M=p1·p2·p3，系数 Ci ≡ C_1(i) (mod p1), …；
- 用 081-数论-中国剩余定理 合并：
- Ci = Σ C_k(i)·M_k·inv(M_k, p_k) (mod M)，M_k = M/p_k。
- 如需目标模 P，最终对 Ci 取模 P。
-
复杂度
- 单次 NTT O(n log n)，卷积总体约 3·O(n log n) + O(n) 乘法。
- 多模 CRT 卷积：常数≈模数个数倍。
-
数值与实现注意
- 乘法与加减取模需用 64 位过渡，或见 090-数论-长整型模乘；powmod/逆元见 091-数论-模幂、088-数论-模逆。
- 预计算所有层的根与逆根可显著减小常数。
- 逆变换必须乘 inv(n)；根方向为正变换用 g^{(p−1)/len}，逆变换用其逆。
- 对输入范围大的整系数卷积，推荐多模 CRT 以避免系数回卷。
- 若题目模数非 NTT 友好，可用多模合并或转用实数 FFT（见 098-数值算法-快速傅里叶变换）。