多项式的运算
定义
简单来说，形如 $ 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 ，满足： $ 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 log_2n) $ 的 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 (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 \]
- -> (5) 中模数平方的原因： 左边多项式模 $ x^{n/2} $ 为 0 代表该多项式每一项最低次数为 n / 2 + 1 。 那么该多项平方后最低次数会是 n + 1 或 n + 2 ， 模 $ x^n $ 后仍为 0 。
于是乎分治，直到 n == 1 ，此时多项式的取模为一个常数，逆元也就是整数的逆元。
其中乘法使用 FFT ，则最终时间复杂度为 $ O(n log_2n) $ 。