文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载本篇技术指南以 cp-algorithms 仓库中 多项式与级数运算 一文为核心骨架系统讲解竞赛编程中常用的多项式乘法、形式幂级数求逆、多项式对数/指数/幂次、多点求值与插值、多项式 GCD 与结式等操作的数学原理、算法推导与复杂度并对照仓库内 FFT 实现、欧几里得算法 等源码级资料给出可复现的实现视角。读完本文你将掌握如何把计数/枚举类问题约化为多项式运算并理解polyT类背后每个核心方法inv、log、exp、eval、inter、resultant的推导过程与实现复杂度。背景为什么竞赛题会约化为多项式运算竞赛编程中的很多问题——尤其是各种枚举enumeration类问题——最终都可以被约化为对多项式与形式幂级数进行运算来求解。这类运算包括最简单的多项式乘法、插值也包括更复杂的多项式对数、多项式指数等。在 cp-algorithms 中这一主题被整理在 src/algebra/polynomial.md并在 src/navigation.md 的代数Algebra章节中与快速傅里叶变换src/algebra/fft.md并列作为Operations on polynomials and series专题收录。本文先建立严格的数学定义再给出基础实现 API随后按算术运算 → 函数计算 → 求值与插值 → GCD 与结式四层递进展开每一层都会给出可推导的公式与复杂度结论。基本概念与事实多项式、卷积与次数一元多项式univariate polynomial是形如 $$ A(x) a_0 a_1 x \dots a_n x^n $$ 的表达式。系数 $a_0,\dots,a_n$ 通常取自某个数集或类似数的结构本文假设系数取自某个域field即加、减、乘、除除数不为 $0$都有良好定义行为与实数类似。最典型的域例子是模素数 $p$ 的剩余类域。为简洁起见本文后续省略一元二字全文只讨论一元情形并尽量用 $A$ 代替 $A(x)$。默认约定要么 $a_n \neq 0$要么 $A(x)0$。乘积与卷积。两个多项式的乘积按算术展开定义 $$ A(x) B(x) \left(\sum\limits_{i0}^n a_i x^i \right)\left(\sum\limits_{j0}^m b_j x^j\right) \sum\limits_{i,j} a_i b_j x^{ij} \sum\limits_{k0}^{nm} c_k x^k C(x). $$ 系数序列 $c_0,c_1,\dots,c_{nm}$ 称为 $a_0,\dots,a_n$ 与 $b_0,\dots,b_m$ 的卷积convolution。次数degree。对满足 $a_n \neq 0$ 的多项式 $A$定义 $\deg A n$为保持一致零多项式 $A(x)0$ 的次数定义为 $\deg A -\infty$。在此约定下对任意多项式 $A,B$ 恒有 $$ \deg AB \deg A \deg B. $$卷积是解决大量枚举问题的基础下面两个典型例子可以直接套用上述定义。例 1两类物体取值计数。第一类物体有 $n$ 个价值为 $a_1,\dots,a_n$第二类物体有 $m$ 个价值为 $b_1,\dots,b_m$。从两类中各取一个问总价值为 $k$ 的取法有多少种解答思路考虑乘积 $(x^{a_1}\dotsx^{a_n})(x^{b_1}\dotsx^{b_m})$。展开后每个单项式恰好对应一个对 $(a_i,b_j)$并对 $x^{a_ib_j}$ 的系数做一次贡献。因此答案就是该乘积中 $x^k$ 的系数。例 2掷骰子求和。掷一枚 $6$ 面骰子 $n$ 次并求和和为 $k$ 的概率是多少解答思路答案是和为 $k$ 的结果数除以总结果数 $6^n$。$n1$ 时结果数可用多项式 $A(x)x^1x^2\dotsx^6$ 表示$n2$ 时沿用上一例的方法得到 $(x^1x^2\dotsx^6)^2$。因此答案就是 $(x^1x^2\dotsx^6)^n$ 的第 $k$ 项系数除以 $6^n$。为便于叙述把 $A(x)$ 中 $x^k$ 项的系数记为 $[x^k]A$。形式幂级数形式幂级数formal power series是不论收敛性、形如 $$ A(x) a_0 a_1 x a_2 x^2 \dots $$ 的无穷和。日常中我们说 $1\frac{1}{2}\frac{1}{4}\frac{1}{8}\dots2$指的是求和项数趋于无穷时收敛到 $2$而形式幂级数只关心构成它的系数序列本身不关心收敛性。两个形式幂级数的乘积同样按算术展开定义 $$ A(x) B(x) \sum\limits_{i,j} a_i b_j x^{ij} \sum\limits_{k0}^{\infty} c_k x^k, $$ 其中每个系数都是有限和 $$ c_k \sum\limits_{i0}^k a_i b_{k-i}. $$ 序列 $c_0,c_1,\dots$ 同样是 $a_0,a_1,\dots$ 与 $b_0,b_1,\dots$ 的卷积只是推广到了无穷序列。由此多项式可以看作只有有限多个非零系数的形式幂级数。形式幂级数在枚举组合学中扮演核心角色通常被作为各类序列的生成函数generating function来研究。虽然生成函数的组合含义不在本文展开范围内但可以给出一个关键直觉若 $A(x)$、$B(x)$ 分别是按对象中原子数量如按顶点数枚举某类对象的生成函数则乘积 $A(x)B(x)$ 枚举的是由 $A$ 类对象与 $B$ 类对象组成的有序对并按对中原子总数计数。例 3石头堆的组合。设 $A(x)\sum_{i0}^{\infty} 2^i x^i$ 枚举每颗石头有 $2$ 种颜色的石头堆大小为 $i$ 的堆有 $2^i$ 个$B(x)\sum_{j0}^{\infty} 3^j x^j$ 枚举每颗石头有 $3$ 种颜色的石头堆。则 $C(x)A(x)B(x)\sum_k c_k x^k$ 枚举的是两堆石头第一堆只含 $A$ 型石头、第二堆只含 $B$ 型石头总数恰为 $k$的对象$c_k$ 即为对应数量。类似地形式幂级数上的其他运算对数、指数等也有对应的组合直觉。多项式长除法与模多项式类似整数除法可以在多项式上定义长除法对任意多项式 $A$ 与非零多项式 $B$可以把 $A$ 唯一表示为 $$ A D \cdot B R,\quad \deg R \deg B, $$ 其中 $R$ 称为 $A$模 $B$ 的余式remainder$D$ 称为商quotient。设 $\deg An$、$\deg Bm$朴素长除法的做法是反复将 $B$ 乘以单项式 $\frac{a_n}{b_m}x^{n-m}$ 并从 $A$ 中减去直到 $A$ 的次数小于 $B$ 的次数。最终剩下的是余式名字由此而来过程中乘过的所有单项式之和构成商。若 $A$ 与 $B$ 模 $C$ 的余式相同称它们模 $C$ 等价记作 $$ A \equiv B \pmod{C}. $$多项式长除法有一组非常实用的性质$A$ 是 $B$ 的倍数当且仅当 $A \equiv 0 \pmod B$$A \equiv B \pmod C$ 当且仅当 $A-B$ 是 $C$ 的倍数特别地由 $A \equiv B \pmod{C \cdot D}$ 可推出 $A \equiv B \pmod{C}$对任意线性多项式 $x-r$恒有 $A(x) \equiv A(r) \pmod{x-r}$因此 $A$ 是 $x-r$ 的倍数当且仅当 $A(r)0$当模为 $x^k$ 时$A \equiv a_0a_1 x\dotsa_{k-1}x^{k-1} \pmod{x^k}$即截断到前 $k$ 项。需要注意长除法无法在形式幂级数上直接定义。不过对任意满足 $a_0 \neq 0$ 的 $A(x)$总存在逆形式幂级数 $A^{-1}(x)$ 使得 $A(x)A^{-1}(x)1$这一事实反过来可用于高效计算多项式的长除法详见后文欧几里得除法一节。仓库中的基础实现polyT类cp-algorithms 配套代码库中提供了多项式代数的完整基础实现核心类是系数类型为T的多项式类polyT。它支持全部平凡运算以及若干实用方法所有算术运算符、-、*、%、/都被重载其中%与/分别表示欧几里得除法中的余式与商。配套的还有modularm类用于在模素数 $m$ 的剩余类上执行算术运算——这与前文系数取自域的假设直接对应modularp正是竞赛中最常用的系数类型。类的公开方法及其复杂度承诺如下以 $n$ 表示所需的系数个数$P(x)$ 表示当前多项式方法功能复杂度deriv()计算导数 $P(x)$线性integr()计算满足 $Q(0)0$ 的不定积分 $Q(x)\int P(x)$线性inv(size_t n)计算 $P^{-1}(x)$ 的前 $n$ 个系数$O(n\log n)$log(size_t n)计算 $\ln P(x)$ 的前 $n$ 个系数$O(n\log n)$exp(size_t n)计算 $\exp P(x)$ 的前 $n$ 个系数$O(n\log n)$pow(size_t k, size_t n)计算 $P^{k}(x)$ 的前 $n$ 个系数$O(n\log nk)$deg()返回 $P(x)$ 的次数常数lead()返回 $x^{\deg P(x)}$ 的系数首项系数常数resultant(polyT a, polyT b)计算 $a$ 与 $b$ 的结式$O(\lvert a\rvert\cdot\lvert b\rvert)$bpow(T x, size_t n)计算 $x^n$—bpow(T x, size_t n, T m)计算 $x^n \pmod m$—chirpz(T z, size_t n)计算 $P(1),P(z),P(z^2),\dots,P(z^{n-1})$$O(n\log n)$vectorT eval(vectorT x)求值 $P(x_1),\dots,P(x_n)$$O(n\log^2 n)$polyT inter(vectorT x, vectorT y)按 $P(x_i)y_i$ 插值多项式$O(n\log^2 n)$其中bpow对应仓库中模幂的经典实现思路参见 src/algebra/module-inverse.md 与 src/algebra/binary-exp.md 的快速幂方法。下面各节逐一推导这些方法背后的算法。算术运算乘法一切方法的地基最核心的操作是两个多项式相乘。给定 $$ A a_0a_1 x\dotsa_n x^n,\quad B b_0b_1 x\dotsb_m x^m, $$ 需要计算 $CA\cdot B$即 $$ C \sum\limits_{i0}^n \sum\limits_{j0}^m a_i b_j x^{ij} c_0 c_1 x \dots c_{nm} x^{nm}. $$朴素卷积是 $O(nm)$ 的而借助快速傅里叶变换FFT可以做到 $O(n\log n)$src/algebra/fft.md 给出了完整的推导与实现且几乎本文所有后续方法都以 FFT 乘法为子程序。FFT 的思路是把多项式从系数表示切换到点值表示对长为 $n$补零到 2 的幂的系数向量计算其在 $n$ 次单位根 $w_n^k$ 处的取值DFT由于点值相乘是对位相乘$A\cdot B$ 在每个点上的取值就是 $A$、$B$ 取值的乘积做一次逐点乘后再做逆 DFT 即可还原乘积的系数。其核心递推是 $T_{\text{DFT}}(n)2T_{\text{DFT}}(n/2)O(n)$由主定理得 $O(n\log n)$逆 DFT 与正变换几乎相同只需用 $w_n^{-k}$ 替换 $w_n^k$最后把所有系数除以 $n$。仓库中 src/algebra/fft.md 给出的multiply实现要点是先把两个向量补零到 $n \ge a.size()b.size()$做两次正变换、逐点乘、一次逆变换最后对复数结果round取整复数运算存在浮点误差。逆级数两种主要方法若 $A(0)\neq 0$总存在无穷形式幂级数 $A^{-1}(x)q_0q_1xq_2x^2\dots$ 满足 $A^{-1}A1$。实际中常常只需要 $A^{-1}$ 的前 $k$ 个系数即模 $x^k$ 计算它。有两种主流算法。分治法Schönhage/Graeffe。对 $B(x)A(x)A(-x)$ 有 $B(x)B(-x)$即 $B(x)$ 是偶多项式——只有偶数次非零系数可写成 $B(x)T(x^2)$。于是 $$ A^{-1}(x) \equiv \frac{A(-x)}{A(x)A(-x)} \equiv \frac{A(-x)}{T(x^2)} \pmod{x^k}. $$ 注意 $T(x)$ 只需一次乘法即可得到之后我们只关心其逆级数的前半系数。于是计算 $A^{-1}\pmod{x^k}$ 被约化为计算 $T^{-1}\pmod{x^{\lceil k/2\rceil}}$复杂度满足 $$ T(n) T(n/2)O(n\log n) O(n\log n). $$Sieveking–Kung 算法Hensel 提升。这一通用过程被称为Hensel 提升Hensel lifting源自 Hensel 引理。所谓提升是指先从满足 $A^{-1}\pmod x$ 的近似 $B_0q_0a_0^{-1}$ 出发再逐步把模从 $x^a$ 提升到 $x^{2a}$。设 $B_k \equiv A^{-1}\pmod{x^a}$下一层近似须满足 $AB_{k1}\equiv 1\pmod{x^{2a}}$可写作 $B_{k1}B_kx^aC$代入得 $$ A(B_kx^aC) \equiv 1 \pmod{x^{2a}}. $$ 记 $AB_k\equiv 1x^aD\pmod{x^{2a}}$则上式蕴含 $D\equiv -AC\pmod{x^a}$进而 $C\equiv -B_kD\pmod{x^a}$。整理出最终迭代公式 $$ B_{k1} \equiv B_k(2-AB_k) \pmod{x^{2a}}. $$ 从 $B_0\equiv a_0^{-1}\pmod x$ 出发$B_k$ 满足 $AB_k\equiv 1\pmod{x^{2^k}}$复杂度同样为 $$ T(n)T(n/2)O(n\log n)O(n\log n). $$ 该算法表面上看比第一种稍复杂但它有非常扎实且实用的推广潜力——正是下一节 Newton 法的特例。欧几里得除法用逆级数求商与余式考虑次数分别为 $n$、$m$ 的多项式 $A(x)$、$B(x)$将 $A$ 写作 $$ A(x) B(x)D(x) R(x),\quad \deg R \deg B. $$ 当 $n\ge m$ 时有 $\deg Dn-m$且 $A$ 的高 $n-m1$ 个系数不参与决定 $R$——也就是说只看 $A$、$B$ 最高处的 $n-m1$ 个系数就可以把 $D(x)$ 作为一个线性方程组解出来。这个方程组可写成带三角结构的矩阵形式 $$ \begin{bmatrix} a_n \ \vdots \ a_{m1} \ a_m \end{bmatrix} \begin{bmatrix} b_m \dots 0 0 \ \vdots \ddots \vdots \vdots \ \dots \dots b_m 0 \ \dots \dots b_{m-1} b_m \end{bmatrix} \begin{bmatrix}d_{n-m} \ \vdots \ d_1 \ d_0\end{bmatrix}. $$引入反转多项式reversed polynomial$$ A^R(x)x^nA(x^{-1})a_na_{n-1}x\dotsa_0x^n, $$ $$ B^R(x)x^mB(x^{-1})b_mb_{m-1}x\dotsb_0x^m, $$ $$ D^R(x)x^{n-m}D(x^{-1})d_{n-m}d_{n-m-1}x\dotsd_0x^{n-m}, $$ 则上述方程组等价于 $$ A^R(x) \equiv B^R(x)D^R(x) \pmod{x^{n-m1}}, $$ 从而可以无歧义地恢复 $D(x)$ 的全部系数 $$ D^R(x) \equiv A^R(x),(B^R(x))^{-1} \pmod{x^{n-m1}}, $$ 再通过 $R(x)A(x)-B(x)D(x)$ 得到余式。值得注意的观察上面的矩阵是三角 Toeplitz 矩阵。求解任意 Toeplitz 矩阵的线性方程组本质上等价于多项式求逆并且该矩阵的逆矩阵仍是三角 Toeplitz 矩阵其元素正是 $(B^R(x))^{-1}\pmod{x^{n-m1}}$ 的系数。多项式函数计算Newton 迭代的统一框架Newton 法Sieveking–Kung 算法可以系统性地推广。考虑方程 $F(P)0$其中 $P(x)$ 是要求的多项式$F(x)$ 是某个多项式值函数定义为其在 $\beta$ 处的展开 $$ F(x) \sum\limits_{i0}^\infty \alpha_i (x-\beta)^i. $$ 可以证明引入新形式变量 $y$ 后 $F(x)$ 可展开为 $$ F(x) F(y) (x-y)F(y) (x-y)^2 G(x,y), $$ 其中 $F(x)$ 是形式幂级数意义上的导数 $$ F(x) \sum\limits_{i0}^\infty (i1)\alpha_{i1}(x-\beta)^i, $$ 而 $G(x,y)$ 是关于 $x,y$ 的某个形式幂级数。设 $F(Q_k)\equiv 0\pmod{x^a}$我们要找 $Q_{k1}\equiv Q_kx^aC\pmod{x^{2a}}$ 使 $F(Q_{k1})\equiv 0\pmod{x^{2a}}$。把 $xQ_{k1}$、$yQ_k$ 代入展开式 $$ F(Q_{k1}) \equiv F(Q_k) (Q_{k1}-Q_k)F(Q_k) (Q_{k1}-Q_k)^2 G(x,y) \pmod{x^{2a}}. $$ 由于 $Q_{k1}-Q_k\equiv 0\pmod{x^a}$其平方 $\equiv 0\pmod{x^{2a}}$于是 $$ 0 \equiv F(Q_{k1}) \equiv F(Q_k)(Q_{k1}-Q_k)F(Q_k) \pmod{x^{2a}}, $$ 得到 $$ Q_{k1} Q_k - \frac{F(Q_k)}{F(Q_k)} \pmod{x^{2a}}. $$因此只要会求多项式逆、会算 $F(Q_k)$就能以 $$ T(n)T(n/2)f(n) $$ 的复杂度求出 $P$ 的前 $n$ 个系数其中 $f(n)$ 是计算 $F(Q_k)$ 与 $F(Q_k)^{-1}$ 的时间通常为 $O(n\log n)$。上面的迭代规则在数值分析中正是著名的Newton 法。Hensel 引理与更广的应用如前所述这个结果的形式化表述是Hensel 引理它可以在更广泛的意义下使用我们工作的其实是一列嵌套环。本文的情形是多项式模 $x$、$x^2$、$x^3$、… 的余式序列另一个典型应用是p-adic 数——那里工作的是一列整数模 $p$、$p^2$、$p^3$、… 的余数序列。例如Newton 法可用于找出给定基下的所有自守数automorphic number平方后以自身结尾的数这个问题可作为练习留给读者经典题目 Square CountryTimus 1698正是 $10$ 进制自守数的判定/构造问题。对数对 $\ln P(x)$ 有经典恒等式 $$ (\ln P(x)) \frac{P(x)}{P(x)}, $$ 于是先求导、求逆、相乘再做不定积分integr()令积分常数 $Q(0)0$即可在 $O(n\log n)$ 内算得 $\ln P(x)$ 的前 $n$ 个系数。逆级数的 Newton 视角逆级数公式其实是 Newton 法的直接特例。取方程 $AQ^{-1}$即令 $$ F(Q)Q^{-1}-A,\quad F(Q)-Q^{-2}, $$ 代入 Newton 迭代得 $$ Q_{k1} \equiv Q_k(2-AQ_k) \pmod{x^{2^{k1}}}, $$ 与前面 Sieveking–Kung 的结论完全一致。指数类似地计算 $e^{P(x)}Q(x)$ 时利用 $\ln QP$取 $$ F(Q)\ln Q-P,\quad F(Q)Q^{-1}, $$ 得迭代 $$ Q_{k1} \equiv Q_k(1P-\ln Q_k) \pmod{x^{2^{k1}}}. $$$k$ 次幂计算 $P^k(x)Q$ 可以借助指数与对数 $$ Q \exp\left[k\ln P(x)\right]. $$但要注意对数与指数只有在能找到初始 $Q_0$ 时才可正确计算而 $Q_0$ 依赖多项式常数项的对数或指数。唯一合理的情形是对 $Q\ln P$ 要求 $P(0)1$从而 $Q(0)0$对 $Qe^P$ 要求 $P(0)0$从而 $Q(0)1$。因此上式仅在 $P(0)1$ 时可直接使用。若 $P(x)\alpha x^t T(x)$ 且 $T(0)1$则可改写为 $$ P^k(x) \alpha^k x^{kt} \exp\left[k\ln T(x)\right]. $$ 顺带一提若还能计算 $\sqrt[k]{\alpha}$例如 $\alpha1$ 时就可以用同样的框架计算多项式的 $k$ 次根。求值与插值Chirp-z 变换在 $z$ 的幂处求值当需要在点 $x_rz^{2r}$ 处求值时可以利用恒等式 $2krr^2k^2-(r-k)^2$ $$ A(z^{2r}) \sum\limits_{k0}^n a_k z^{2kr} z^{r^2}\sum\limits_{k0}^n (a_k z^{k^2}), z^{-(r-k)^2}. $$ 除去因子 $z^{r^2}$这正是序列 $u_ka_k z^{k^2}$下标 $0..n$与 $v_kz^{-k^2}$下标 $-n..m$$m$ 为所需的最大 $z$ 幂次的卷积。若需要在 $x_rz^{2r1}$ 处求值做变换 $a_k\to a_k z^k$ 即可归约到前一种情形。这给出 $O(n\log n)$ 的算法因而可以用卷积实现非 2 的幂长度的 DFT。另一个观察是 $kr\binom{kr}{2}-\binom{k}{2}-\binom{r}{2}$于是 $$ A(z^r) z^{-\binom{r}{2}}\sum\limits_{k0}^n \left(a_k z^{-\binom{k}{2}}\right) z^{\binom{kr}{2}}. $$ 若定义多项式 $A_0(x)\sum_{k0}^n a_{n-k}z^{-\binom{n-k}{2}}x^k$ 与 $A_1(x)\sum_{k\ge0}z^{\binom{k}{2}}x^k$则 $A_0(x)A_1(x)$ 中 $x^{nr}$ 的系数恰为 $z^{\binom{r}{2}}A(z^r)$。计算时可用递推 $z^{\binom{k1}{2}}z^{\binom{k}{2}k}$ 来生成 $A_0$、$A_1$ 的系数。多点求值Multi-point Evaluation要求 $A(x_1),\dots,A(x_n)$。核心事实是 $A(x)\equiv A(x_i)\pmod{x-x_i}$做法如下构建一棵线段树使线段 $[l,r)$ 上存储乘积 $P_{l,r}(x)(x-x_l)(x-x_{l1})\dots(x-x_{r-1})$从根节点$l1,rn1$当前多项式为 $A(x)\bmod P_{1,n1}(x)A(x)$开始设 $m\lfloor(lr)/2\rfloor$携带 $A(x)\pmod{P_{l,m}(x)}$ 下移到 $[l,m)$递归计算出 $A(x_l),\dots,A(x_{m-1})$对 $[m,r)$ 同理携带 $A(x)\pmod{P_{m,r}(x)}$拼接两次递归的结果并返回。整个过程总复杂度 $O(n\log^2 n)$。插值Interpolation给定点值对 $(x_i,y_i)$Lagrange 插值公式给出 $$ A(x) \sum\limits_{i1}^n y_i \prod\limits_{j\neq i}\frac{x-x_j}{x_i-x_j}. $$ 直接计算很困难但可以用分治在 $O(n\log^2 n)$ 内完成。考虑 $P(x)(x-x_1)\dots(x-x_n)$$A(x)$ 中各项分母正是乘积 $$ P_i \prod\limits_{j\neq i}(x_i-x_j). $$ 关键观察$P(x_i)P_i$——于是可以复用上面的多点求值在 $O(n\log^2 n)$ 内求出全部 $P_i$。接下来在多点求值所用的同一棵线段树上递归叶节点存放 $\frac{y_i}{P_i}$从递归返回时用公式 $$ A_{l,r} A_{l,m}P_{m,r}P_{l,m}A_{m,r} $$ 合并左右子树的结果。回到根节点时恰好得到 $A(x)$。整个过程同样是 $O(n\log^2 n)$。GCD 与结式给定 $A(x)a_0a_1x\dotsa_nx^n$ 与 $B(x)b_0b_1x\dotsb_mx^m$。设 $\lambda_0,\dots,\lambda_n$ 为 $A$ 的根含重数$\mu_0,\dots,\mu_m$ 为 $B$ 的根含重数。问题如何判断 $A$ 与 $B$ 是否有公共根有两种相互关联的做法。欧几里得算法仓库中已有关于欧几里得算法的完整文章src/algebra/euclid-algorithm.md。对任意满足条件的整环domain欧几里得算法可写得极其简洁templatetypename T T gcd(const T a, const T b) { return b T(0) ? a : gcd(b, a % b); }对多项式 $A(x)$、$B(x)$ 而言可以证明该算法在 $O(nm)$ 内终止。注意这里的%需要是欧几里得除法余式语义即前文欧几里得除法一节描述的%运算符。结式Resultant计算乘积 $A(\mu_0)\cdots A(\mu_m)$它为零当且仅当某个 $\mu_i$ 是 $A(x)$ 的根即两多项式有公共根。为保持对称再乘上 $b_m^n$整个乘积可重写为 $$ \mathcal{R}(A,B) b_m^n\prod\limits_{j0}^m A(\mu_j) b_m^n a_m^n \prod\limits_{i0}^n \prod\limits_{j0}^m (\mu_j-\lambda_i) (-1)^{mn} a_n^m \prod\limits_{i0}^n B(\lambda_i). $$ 这个值称为 $A(x)$ 与 $B(x)$ 的结式resultant。由定义可推出四条性质$\mathcal R(A,B) (-1)^{nm}\mathcal R(B,A)$当 $n0$ 或 $m0$ 时$\mathcal R(A,B)a_n^m b_m^n$若 $b_m1$则对任意多项式 $C(x)$ 且 $n,m\ge1$$\mathcal R(A-CB,B)\mathcal R(A,B)$由 3 可推得对任意 $A,B,C$$\mathcal R(A,B)b_m^{\deg(A)-\deg(A-CB)}\mathcal R(A-CB,B)$。一个奇迹般的推论是两个多项式的结式始终与其系数同环。同时这些性质允许我们沿着欧几里得算法的过程同步计算结式总复杂度 $O(nm)$。仓库文档给出的实现如下templatetypename T T resultant(polyT a, polyT b) { if(b.is_zero()) { return 0; } else if(b.deg() 0) { return bpow(b.lead(), a.deg()); } else { int pw a.deg(); a % b; pw - a.deg(); base mul bpow(b.lead(), pw) * base((b.deg() a.deg() 1) ? -1 : 1); base ans resultant(b, a); return ans * mul; } }注意其中的符号修正当 $b.deg()$ 与 $a.deg()$ 均为奇数时即 $(-1)^{nm}$ 中的指数 $nm$ 为奇数乘上 $-1$。这里bpow即前文 API 表中的快速幂。Half-GCD 算法存在能在 $O(n\log^2 n)$ 内计算 GCD 与结式的方法。其过程实现一个 $2\times 2$ 线性变换把多项式对 $(a(x),b(x))$ 映射到另一对 $(c(x),d(x))$满足 $\deg d(x)\le \frac{\deg a(x)}{2}$。只要足够小心任何多项式对的 half-GCD 都可用至多 2 次递归调用完成而参与递归的多项式至少缩小一半。算法细节较为繁琐但库中已提供half_gcd函数实现。实现好 half-GCD 后反复应用直到约化到 $(\gcd(a,b),0)$ 这对即可。复杂度速查与仓库配套资源操作复杂度关键方法多项式乘法$O(n\log n)$FFT见 src/algebra/fft.md逆级数前 $n$ 项$O(n\log n)$inv分治 / Sieveking–Kung多项式对数 / 指数 / $k$ 次幂$O(n\log n)$log/exp/pow欧几里得除法商 余式$O(n\log n)$基于逆级数$D^R\equiv A^R(B^R)^{-1}$多项式求导 / 积分$O(n)$deriv/integrChirp-z 求值$O(n\log n)$chirpz多点求值 / 插值$O(n\log^2 n)$eval/inter多项式 GCD / 结式$O(nm)$朴素、$O(n\log^2 n)$Half-GCDresultant/half_gcd这些方法的正确性可以由配套测试覆盖到仓库的 test/ 目录包含test_fft.cpp等测试程序test.sh与extract_snippets.py负责从文档提取代码片段并编译运行可作为读者验证实现、加深理解的入口。相关练习问题下面这些问题直接应用了本文的算法适合作为巩固练习题目名保留自原文档的问题清单CodeChef – RNGCodeForces – Basis ChangeCodeForces – PermutantCodeForces – Medium Hadron Collider赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐Learn-Algorithms 数值问题面试题全解位运算、幂运算、素数分解与大数处理实战指南Learn Algorithms 数值问题面试题全解位运算、幂运算、素数分解与大数处理实战指南 导读 本文以《Learn Algorithms》仓库中 9 A教程Julia 数值运算与初等函数完全指南运算符、比较、优先级与数值转换Julia 数值运算与初等函数完全指南运算符、比较、优先级与数值转换 导读 本文以 Julia 官方手册 doc/src/manual/mathematica编程语言编译器语言运行时标准库JIT编译cosmos 仓库中的 Newton 多项式插值算法基于均差的实现与验证指南cosmos 仓库中的 Newton 多项式插值算法基于均差的实现与验证指南 导读 本文以 cosmos https://link.gitcode.com/i教程示例工程上一篇告别复杂动画逻辑Bevy状态机如何让角色动起来像呼吸一样自然下一篇如何利用ClickHouse进行游戏数据分析玩家行为与运营指标分析的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考