多项式的运算

发表于 2019-10-01 更新于 2019-12-08 阅读次数：

定义

简单来说，形如 $a_{0} + a_{1} X + a_{2} X^{2} + . . . + a_{n} X^{n}$ 的代数表达式叫做多项式，可以记作 $P (X) = a_{0} + a_{1} X + a_{2} X^{2} + . . . + a_{n} X^{n}$ （系数表示法）， a 叫做多项式的系数，X 是一个不定元，不表示任何值，不定元在多项式中最大项的次数称作多项式的次数。

加减

两个多项式 a, b 的和 a + b 是一个多项式 c ，满足： $x, c (x) = a (x) + b (x)$

两个多项式 a, b 的差 a - b 是一个多项式 c ，满足： $x, c (x) = a (x) - b (x)$

多项式的加减十分自然，实际运算中也只需要按定义 O(n) 枚举即可。

乘

两个多项式 a, b 的积 a * b 是一个多项式 c ，满足： $x, c (x) = a (x) b (x)$

此时将 a, b 的系数按分配率展开求 c 的时间复杂度为 O(n * m) ， n, m 分别为 a, b 的次数，不难得出 c 的次数为 n + m 。

快速求多项式乘积的方法是 $O (n l o g_{2} n)$ 的 FFT 或 NTT 。

除

两个多项式 a, b 的商 a / b 是一个多项式 c ，满足： $x, c (x) = a (x) / b (x)$

众所周知多项式除法可以列竖式求解，这样做与乘法一样复杂度为 O(n * m) 。

取模

正如整数除法会有余数，多项式除法也不一定整除，此时 a / b 会余一个多项式 c ，正如整数除法中余数小于除数，此处也要满足 c 的次数小于 b 的次数以保证唯一性。

具体来说，对于多项式 a, b 存在唯一的多项式 c, d 满足： a = b * d + c 且 c 的次数小于 b 的次数，便称 c 是 b 除 a 的余数，即 a 模 b 的结果， d 是 b 除 a 的商。

值得注意的是，当模数 b 可表示为 $b (x) = x^{k}$ 时， a 模 b 相当于将 a 舍弃所有次数大于等于 k 的单项式的结果。

逆元

对于多项式 a ，其在 mod p 意义下的逆元 b 满足： a * b mod p = 1 且 b 的次数不比 a 大（此处的 1 实际上是指只有常数项为 1 而次数为 0 的多项式）， a 的逆元通常记为 $a^{- 1}$ 或 inv(a) 。

那么在 mod p 意义下，有 $a / b = a b^{- 1}$ 。

逆元的求解

事实上模数一般是 $x^{n}$ 。

此时可以用分治求多项式 a 的逆元 b。

假设已经分治求得了 a 模 $x^{n / 2}$ （此处及以下除法表示向上取整）的逆元 c 。那么有： $a \cdot c \equiv 1 (m o d x^{n / 2}) (1)$ 由 b 的定义可知： $a \cdot b \equiv 1 (m o d x^{n}) (2)$ 转换为： $a \cdot b \equiv 1 (m o d x^{n / 2}) (3)$ (3) - (1) 得： $b - c \equiv 0 (m o d x^{n / 2}) (4)$ 两边同时平方得： $b^{2} - 2 b c + c^{2} \equiv 0 (m o d x^{n}) (5)$ 两边同时乘 a 得： $b - 2 c + c^{2} a \equiv 0 (m o d x^{n}) (6)$ 移项，整理： $b = (2 c - c^{2} a) m o d x^{n}$

-> (5) 中模数平方的原因：左边多项式模 $x^{n / 2}$ 为 0 代表该多项式每一项最低次数为 n / 2 + 1 。那么该多项平方后最低次数会是 n + 1 或 n + 2 ，模 $x^{n}$ 后仍为 0 。

于是乎分治，直到 n == 1 ，此时多项式的取模为一个常数，逆元也就是整数的逆元。

其中乘法使用 FFT ，则最终时间复杂度为 $O (n l o g_{2} n)$ 。