NTT 与多模数与多项式高级操作

• 多项式求逆的倍增长公式
• 利用求逆 + 微积分实现 ln/exp
• 牛顿迭代的复杂度递推

多项式求逆（模 x^n）：g0 为常数项逆元，递推 g_{k+1} = g_k(2 − f·g_k) mod x^{2k}，每轮长度翻倍。多项式除法：f = g·q + r，取反转后 q = rev(f)·rev(g)^{-1}。ln f：ln f = ∫ f'/f，即求导、求逆、卷积、积分。exp f：exp f = g 满足 g' = g·f'，用牛顿迭代 g_{k+1} = g_k(1 − ln g_k + f) mod x^{2k}。复杂度：每轮 O(M(2k))，M(n) 为卷积复杂度（NTT 下 O(n log n)），总复杂度 T(n) = T(n/2) + O(n log n) = O(n log n)。所有运算都建立在卷积 O(n log n) 之上。

牛顿迭代的核心是"倍增 + 每轮一次或两次卷积"，长度每轮翻倍，几何级数求和使总复杂度仍为 O(n log n)。除法、ln、exp 都归约到求逆与卷积，体现了"把高级运算降到求逆 + 微积分"的代数思想。复杂度关键：各轮长度 2^k 的卷积求和 = O(n log n)。

• 生成函数与多项式乘法
• 卷积系数的组合意义
• 常见建模模板（组合、排列、EGF）

把每种"选择"对应一个多项式，多项式的系数表示"选择若干对象的方案数"，两个多项式相乘时其卷积系数 c_k = Σ a_i·b_{k−i} 恰好表示"从 A 中取 i 个、从 B 中取 k−i 个的总方案数"。这样"组合多个独立部件"的计数 = 多项式乘法。常见模板：普通生成函数 OGF（x 的指数为选的数量，适用于组合/划分）；指数生成函数 EGF（系数除以 k!，适用于排列/有标号对象）；多项式幂、求逆、ln/exp 对应组合的拼接、组合、置换等。建模时把"每个对象/部件"的生成函数写出来，目标计数 = 各函数乘积（或复合）的特定系数。

生成函数把计数问题转化为"多项式运算"，卷积系数天然对应"分步组合"的方案数。工程上先写出每个部件的生成函数，再通过乘法/卷积/取名获得目标系数。这是"把组合计数落到多项式算法"的核心范式，配合 NTT 实现 O(n log n) 的系数计算。

• FWT 的三种卷积（XOR/AND/OR）变换
• 子集卷积 SOS DP
• 正逆变换模板

FWT 处理形如 c_k = Σ_{i op j = k} a_i b_j 的卷积，其中 op 为 XOR/AND/OR。做法是先把数组用对应的变换（FWHT for XOR、and 变换、or 变换）转为频域，逐点相乘，再逆变换回来，全程 O(n log n)。例如 OR 卷积：正向变换做"子集和"（SOS DP，对每个维度累加子集），逆变换做"子集差"（容斥）。AND 卷积类似。XOR 用 Hadamard 变换（±1 矩阵）。子集卷积则额外用"按 popcount 分层 + FWT"处理，保证子集不重叠。这三者都是 O(n log n)（n 为 2^m 的数组）。

FWT 三兄弟与 FFT 思想一致：变换到频域使"卷积"变成"逐点乘"，再逆变换。变换矩阵不同（OR/AND 用格论，XOR 用 Hadamard）。SOS DP 是 OR/AND 卷积的快速实现。工程上模板需分别实现三种正向/逆向 transform，并注意取模。

• 原根替代单位根
• bit-reverse 重排
• 蝶形运算的工程实现

NTT 用模数 p 的原根 g 的幂作为单位根（ω = g^{(p−1)/n}），替代 FFT 的复数单位根，从而在模意义下做整数卷积。实现分三步：先 bit-reverse 重排输入（把下标二进制反转），再做自底向上的蝶形运算（每层合并两个子数组，用旋转因子 ω 加权），最后若逆变换需乘以 n^{-1}。全程 O(n log n)，且无浮点误差、结果精确。工程要点：n 取 2 的幂，预处理旋转因子表，逻辑采用"分治蝶形"。

bit-reverse 重排让蝶形运算可以原地迭代进行，避免递归。原根保证 ω^n = 1 且各阶不同，满足 DFT 性质。NTT 相比 FFT 的优势是整数精确、无精度问题，适合模卷积。工程上 998244353 等 NTT 友好模数提供原根 3。

• ln 需要对常数项求逆（需非零）
• exp 的定义需常数项为 0
• 常数项可归一化的处理

ln f 的导数 f'/f 需要 f 的逆，而多项式求逆要求 f 常数项非零（否则无逆）；且 ln f 的常数项为 ln(f0)，若 f0 ≠ 1 需先归一化。exp f 的形式幂级数定义为 Σ f^k/k!，要求 f 常数项为 0（否则 exp(f0) 无定义或引入非形式幂级数），即 g(0)=1。若 f 常数项为 c ≠ 1，可先提取 c：ln f = ln c + ln(f/c)，exp 同理先归一化常数项。常数项为 0 时 ln 无定义（f0=0 无逆）、exp 正常（f0=0 满足条件）。处理：ln 要求 f0≠0（可归一化到 1），exp 要求 f0=0。

形式幂级数运算的合法性取决于常数项：求逆需要常数项可逆（非零），ln 基于求逆故需 f0≠0 且归一化到 1；exp 的定义要求 f0=0。理解"常数项条件"是正确使用 ln/exp 的前提，工程上常先提取常数项再运算。

• NTT 用原根替代复数单位根
• 模卷积的精确性优势
• 998244353 的 NTT 友好性质

FFT 用复数单位根 ω=e^{2πi/n} 计算 DFT，存在浮点误差；NTT 在模素数 p 下，用 p 的原根 g 的幂 ω = g^{(p−1)/n} 作为 n 次单位根，性质（ω^n=1、各阶不同）与复数单位根一致，从而在模 p 意义下做整数卷积，无浮点误差、结果精确。998244353 是常用模数，因为 998244353 = 119·2^23 + 1，p−1 有 2^23 的因子，能支持长度到 2^23 的 NTT，且 3 是它的原根。这样的"NTT 友好素数"（p = k·2^m + 1）保证有足够大的 2 的幂次单位根。

NTT 是 FFT 在有限域上的对应物，把"复数单位根"换成"模 p 的原根幂"。998244353 因 2 的幂次因子大、原根为 3、模数规模适中，成为竞赛与工程的标准 NTT 模数。整系数卷积用 NTT 可避免浮点误差。

• 牛顿迭代的代数推导
• 误差平方收敛（模 x^{2k} 翻倍）
• 复杂度递推求解

设 f 常数项非零，求 f 的逆 g（模 x^n）。从 g0 = f(0)^{-1}（模 x^1）出发，若 g_k 满足 f·g_k ≡ 1 mod x^k，则令 g_{k+1} = g_k(2 − f·g_k) mod x^{2k}。验证：1 − f·g_{k+1} = (1 − f·g_k)² mod x^{2k}，因为误差是 x^k 的倍数，平方后是 x^{2k} 的倍数，故误差阶数翻倍，称为"误差平方收敛"。复杂度递推：每轮需要一次多项式乘法 O(M(2k))，总复杂度 T(n) = T(n/2) + O(n log n) = O(n log n)（几何级数求和）。每轮只需一次卷积（2−f·g 可先算 f·g 再组合）。

牛顿迭代的妙处是"误差平方"：已知模 x^k 的逆，能推出模 x^{2k} 的逆，长度翻倍。配合卷积 O(n log n)，总复杂度仍是 O(n log n)。这是多项式求逆、除法、exp 等所有可倍增运算的共同数学基础。

• 拆系数法（将系数拆高位/低位）
• 三模数 CRT 重构
• 精度与速度取舍

当模数不是 NTT 友好素数时，用 MTT 处理。两种主流方法：一是三模数 CRT 法——选三个 NTT 友好素数（如 998244353、1004535809、469762049），分别做 NTT 卷积，再用 CRT 把三个结果重构到原模数；二是拆系数法——把系数 a 拆成 a = a1·B + a0（B 取 √M 量级），把 a1、a0 与 b1、b0 组合成若干长序列做 FFT（或 NTT），用 4 次（或 3 次）FFT 得到精确结果。精度上：拆系数法用浮点 FFT 需控制误差，三模数 CRT 用整数 NTT 精确无误差；速度上：拆系数法常数小、速度快，三模数 CRT 需 3 次 NTT 较慢但精确。取模任意是两者共同目标。

三模数 CRT 用"多个 NTT 友好素数分别卷积再重构"，整数精确但三次 NTT 带来较大常数；拆系数法把大系数拆开避免浮点溢出，用 3~4 次 FFT 精度可控、速度较快。选型：精度要求高用三模数，速度要求高且值域可控用拆系数。

• 系数拆分 a = a1·B + a0
• 把大系数乘积分解为小系数卷积
• 精度控制与 FFT 次数

任意模数 NTT 拆系数法把每个系数 a 拆成 a1·B + a0（B 取约 √M，M 为最大可能值），则 a·b = (a1·B+a0)(b1·B+b0) = a1b1·B² + (a1b0+a0b1)·B + a0b0。分开计算 a1b1、a1b0、a0b1、a0b0 四个卷积，其中每个卷积的系数都是"小系数"（≤B 量级）的卷积，数值范围小，浮点 FFT 的误差可控（不会溢出 double 精度）。通过复用 FFT 可把 4 次 FFT 优化到 3 次（或 4 次 NTT）。因为拆开后涉及的最大乘积只有 O(B²) 量级，远小于原始大系数的乘积，所以避免了精度问题。

精度问题的根源是"大系数相乘产生更大的中间值，超出浮点精度范围"。拆系数把大数拆成"高位×B + 低位"，使卷积中的每个中间值都缩小到 O(B²)，double 能精确表示。于是用少量 FFT 即可得到精确卷积结果，兼顾任意模数与精度。

• NTT 友好素数条件 p = k·2^n + 1
• 原根求解与检验
• 工程模板

NTT 友好素数需满足 p = k·2^n + 1（p−1 含大的 2 的幂因子），这样模 p 下有足够大的 2 的幂次单位根，支持长度为 2^n 的 NTT。常见如 998244353 = 119·2^23 + 1。原根求解：暴力枚举 g（从 2 起），对 p−1 的每个素因子 d，检验 g^{(p−1)/d} ≠ 1 mod p；若全部不满足则 g 是原根。对 NTT 而言只需满足 g^{(p−1)/2} ≠ 1（即 g 不是二次剩余）即可作为 2 的幂次单位根生成元。工程上原根常查表（如 3），或按上述条件筛选。

2 的幂因子大小决定 NTT 最大长度。原根检验基于"g 的阶整除 p−1"的数论性质，遍历 p−1 的素因子即可验证。对 NTT 友好的素数，p−1 只有少数素因子，检验很快。工程上直接查已知原根或实现筛选。

• Bluestein 算法把任意长度 DFT 转为卷积
• chirp-z 变换
• 非 2 的幂长度的处理

Bluestein 算法（chirp-z 变换）把任意长度 n 的 DFT 转化为一次卷积：利用公式 nk = (n²+k²−(n−k)²)/2，把 DFT 表示成两个 chirp 序列的卷积形式，再用 FFT/NTT 计算卷积。它解决"长度不是 2 的幂时无法直接做基 2 FFT/NTT"的问题，把任意长度变换归约为一次长度大约 2n 的卷积（可补零到 2 的幂）。工程上需构造两个 chirp 序列、用 NTT 做卷积、再依公式还原。O(n log n)。

基 2 FFT 要求长度是 2 的幂，Bluestein 通过代数恒等式把任意长度 DFT 转成卷积，从而复用 FFT/NTT。这在需要精确整数卷积（NTT）且长度非 2 的幂时很有用。工程上构造 chirp 序列 + 一次卷积 + 还原。

• 三个 NTT 友好素数分别卷积
• CRT 重构整系数
• O(n log n) 复杂度

多模数 MTT 选三个 NTT 友好素数 p1,p2,p3（范围足够大，确保真实卷积系数在乘积范围内），分别做三次 NTT 卷积得到 c 模 p1,p2,p3 的值。然后用 CRT 把三个模余数重构为真实整数系数，再对目标模数 M 取模。CRT 重构：求出同时满足三个模同余的整数，可用扩展欧几里得逐步合并，或预计算各模逆元做线性组合。复杂度 O(n log n)（三次 NTT 都 O(n log n)，CRT 重构每系数 O(1)）。工程上要小心系数范围：三个素数乘积需大于真实系数最大值，避免进位误判。

三模数 MTT 的核心是"用多个可取模的域做卷积，再合并"，保证整系数精确。三次 NTT 是常数代价，CRT 重构是线性。工程要点：选三个模数乘积足够大、正确处理 CRT 合并，即可得到任意模数下的精确卷积。

• exp 的牛顿迭代公式
• 依赖求逆与 ln
• 复杂度分析

多项式 exp f（f 常数项为 0）的牛顿迭代：g_{k+1} = g_k(1 − ln g_k + f) mod x^{2k}，从 g0=1 开始，每轮长度翻倍。每轮需要求 ln g_k（用到求逆与卷积）与一次卷积，复杂度 O(M(2k))。总复杂度 T(n) = T(n/2) + O(n log n) = O(n log n)。工程上实现 exp 需先实现求逆与 ln，再按牛顿迭代倍增。注意 f 常数项必须为 0，否则先归一化。

exp 的牛顿迭代把问题归约到"求 ln + 卷积"，而 ln 又依赖求逆，因此 exp 是多项式运算中较复杂的一环，但仍是 O(n log n)。工程实现按"求逆 → ln → exp"的依赖顺序搭建，每次迭代长度翻倍。

• ln f = ∫ f'/f
• 求导、求逆、卷积、积分
• 复杂度

多项式 ln f 用公式 ln f = ∫ f'/f：先对 f 求导得 f'（O(n)），再求 f 的逆（牛顿迭代 O(n log n)），两者卷积得 f'/f（O(n log n)），最后积分（O(n)）。总 O(n log n)。前提：f 常数项非零且归一化到 1（否则 ln f 常数项为 ln f0，需处理）。工程上依赖求逆与卷积，实现简单直接。

ln 通过"导数 + 逆 + 卷积 + 积分"四条微积分操作实现，把对数运算归约到求逆。这是 O(n log n) 的首要依赖是求逆。理解 ln 的实现即可明白 exp 为何依赖 ln 与求逆。

• 反转多项式 trick
• 除法转求逆
• 复杂度

多项式除法 f = g·q + r（deg f = n, deg g = m, deg q = n−m）。用反转（reversal）技巧：rev(f) = rev(g)·rev(q) + x^{n−m+1}·rev(r)。取模 x^{n−m+1} 后 rev(r) 项消失，得 rev(q) ≡ rev(f)·rev(g)^{-1} mod x^{n−m+1}，于是商 q = rev(rev(f)·rev(g)^{-1})，再回代求余 r = f − g·q。核心是求 rev(g) 的逆（O(n log n)）与卷积。总 O(n log n)。

多项式除法把"除法"转化为"求逆 + 卷积"：反转技巧让商多项式成为逆的乘积，从而消去余项。这体现了多项式运算的相互归约（除法依赖求逆）。工程上实现反转、求逆、卷积即可得到除法。

• dp 递推的卷积形式
• CDQ 分治先处理左半贡献再贡献右半
• 边界处理

当 dp[i] = Σ_{j<i} dp[j]·g[i−j] 时，直接计算 O(n²)。CDQ 分治优化：分治处理区间 [l,r]，先递归处理左半 [l,mid] 得到 dp[l..mid]；然后用一次卷积算出左半对右半 [mid+1,r] 的贡献（把左半的 dp 与 g 卷积，加到右半对应位置）；再递归处理右半。每层做一次卷积 O(n log n)，总 O(n log² n)。边界：分治到单点时 dp 已确定（或直接算出），递归返回时把左半贡献累加；注意 g 的索引变换（贡献 dp[j]·g[i−j] 到 dp[i] 需 i−j = i−j，用卷积数组对齐）。

CDQ 分治把"左侧贡献右侧"的 DP 转移用卷积批量加速，把 O(n²) 降到 O(n log² n)。每层一次卷积，层数 log n。边界处理要点：单点间到点后不再递归；下推贡献时用卷积结果按偏移累加，避免重复计算。这是分治 FFT/CDQ 优化 DP 的标准框架。

• g 的递推公式
• 模 x^(2k) 的倍增
• 初始条件

多项式求逆的倍增递推：g0 = f(0)^{-1}（模 x^1）；对 k 从 0 开始，g_{k+1} = g_k·(2 − f·g_k) mod x^{2^{k+1}}。每轮把已知逆的精度从模 x^{2^k} 提升到模 x^{2^{k+1}}，直到达到 x^n。复杂度每轮一次卷积 O(M(2^k))，总 O(n log n)。实现时每轮需做一次 f·g_k 的卷积（截断到 2^{k+1} 长度）。

递推公式 g_{k+1} = g_k(2 − f·g_k) 是牛顿迭代对"求逆"的实例化：若 f·g_k ≡ 1 mod x^k，则 f·g_{k+1} ≡ 1 mod x^{2k}，误差平方。这是所有多项式求逆实现的基础公式。

• f^k = exp(k·ln f)
• 常数项为 1 的原因
• 常数项非 1 的处理

多项式快速幂 f^k 用 f^k = exp(k·ln f)：先求 ln f，乘以 k，再 exp。这要求 ln f 可定义，即 f 常数项为 1（且非零），因为 ln 需要常数项归一化为 1 才令 ln 的常数项为 0，exp 才良定义。若 f 常数项为 c ≠ 1，则 f = c·(f/c)，取 f^k = c^k·(f/c)^k，其中 f/c 常数项为 1，可再用 exp(k·ln(f/c))。复杂度 O(n log n)。

ln/exp 组合的标准流程依赖常数项为 1（或归一化）。工程上先提取常数因子 c，把底数归一化到常数项 1，再 ln→乘 k→exp，最后乘 c^k。这样保证形式幂级数运算合法。