核心概述
多项式代数（Polynomial Algebra）覆盖多项式的系数表示、加减乘除（卷积与带余除法）、求值与多点变换、GCD 与级数运算（逆、开方、ln、exp 等），在可用域下可用 FFT/NTT 将主要操作加速至近线性时间。
原文引述
Description: Polynomial algebra with coefficient representation: add, multiply (FFT/NTT), evaluation, interpolation, division with remainder, GCD, and series operations (inverse, sqrt, log, exp) via Newton iteration. Time: Multiply O(n log n); divide O(n log n); series ops O(n log n) each Status: tested ——摘自本节点现有英文注释
展开阐述
-
数据结构（据实现）
- struct Poly：vector
coeff；支持 trim()（去除尾部零）、deg()（次数）、operator[] 访问。 - 可选：mod 域包装（T=ModInt）自动取模；大整数版（__int128 或 BigInt）。
- struct Poly：vector
-
基本操作
- 加/减法：同度数向量逐项加减；对齐维度。
- 乘法：系数卷积，通过 098-数值算法-快速傅里叶变换（复数）或 099-数值算法-模域FFT（模域）加速，或朴素 O(n^2)。
- 求值：
- Horner 法：O(n)；
- 多点求值：用 FFT/NTT 或快速子集变换加速 O(n log^2 n)（实现可选）。
- 插值：见 110-数值算法-多项式插值。
-
多项式除法（带余）
- 给定 A, B (deg B ≤ deg A)，求 Q,R 使 A = Q·B + R，deg R < deg B。
- 逆序法：设 Arev(x)=x^{deg A}·A(1/x)，Brev(x)=x^{deg B}·B(1/x)。
- Qrev(x) = Arev(x) / Brev(x)（在模 x^{deg A−deg B+1} 下的除法）。
- Q(x) = x^{deg A−deg B}·Qrev(1/x)。
- R = A − Q·B。
- 复杂度 O(n log n)（依赖卷积）。
-
多项式 GCD
- 模下：类似整数 GCD，用欧几里得算法，每次除法用多项式除法实现。
- 可用余数序列降次，必要时用伪余数（乘以首项系数幂）保持整系数。
-
幂级数运算（Newton 迭代）
- 逆：设 F·G = 1 (mod x^k)，已知 G mod x^{⌈k/2⌉} 求 G mod x^k：
- G_new = G·(2 − F·G) (mod x^k)。
- 开方：设 G^2 = F (mod x^k)，已知 G mod x^{⌈k/2⌉}：
- G_new = (G + F·inv(G))·inv(2) (mod x^k)。
- ln 与 exp：通过积分/微分与逆/乘法组合实现（见模板）。
- 每次迭代复杂度 O(k log k)，总 O(n log n)。
- 逆：设 F·G = 1 (mod x^k)，已知 G mod x^{⌈k/2⌉} 求 G mod x^k：
-
输出语义
- 所有操作返回 Poly 对象，系数按升幂排列（a_0 + a_1 x + …）。
- 除法返回 {Q, R} 或仅 Q（依接口）。
-
复杂度
- 加减 O(n)；乘法 O(n log n)；除法 O(n log n)；求值 O(n) 或 O(n log^2 n) 批量；系列运算 O(n log n)。
-
使用与注意
- 模域：所有运算在模内进行，见 094-数论-模运算 与 099-数值算法-模域FFT。
- 首项系数：系列运算要求常数项可逆（如逆、开方）。
- 规范化：操作后 trim() 去除尾部零，保持 deg 正确。
- 卷积实现：复数 FFT 有舍入误差；模域 NTT 精确但需友好模数。