定义

简单来说,形如 $ a_0 + a_1X + a_2X^2 + … + a_nX^n $ 的代数表达式叫做多项式,
可以记作 $ P(X) = a_0 + a_1X + a_2X^2 + … + a_nX^n $ (系数表示法),
a 叫做多项式的系数,X 是一个不定元,不表示任何值,
不定元在多项式中最大项的次数称作多项式的次数。

加减

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

两个多项式 a, b 的差 a – b 是一个多项式 c ,满足:
$ \forall x, c(x) = a(x) – b(x) $

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

两个多项式 a, b 的积 a * b 是一个多项式 c ,满足:
$ \forall x, c(x) = a(x) \cdot b(x) $

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

快速求多项式乘积的方法是 $ O(n \cdot log_2n) $ 的 FFT 或 NTT 。

两个多项式 a, b 的商 a / b 是一个多项式 c ,满足:
$ \forall 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 \cdot b^{-1} $ 。

逆元的求解

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

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

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

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

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

其中乘法使用 FFT ,则最终时间复杂度为 $ O(n \cdot log_2n) $ 。


4 条评论

syscon · 2019年1月29日 上午8:11

逆元的乘法是用 NTT 吧

    Kewth · 2019年1月29日 上午8:58

    啊有什么区别吗?不太清楚

      syscon · 2019年2月10日 下午7:44

      NTT 一般用于取模的多项式相乘

FFT – Kewth's blog · 2019年1月28日 下午9:13

[…] 多项式 […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: