多项式可以加减乘，这是基本常识。然而，多项式还支持除法、乘方、开方、求对数等等运算，这可实在是有些神奇。于是在此小结一下多项式的诸多运算。在接下来的叙述中，定义多项式$A(x) = \sum_{i=0}^{n} {a_i x^i}$。

为方便叙述，在下列所有运算中，多项式的运算均定义在$\pmod {x ^ n}$意义下，整数的运算均定义在$\pmod P$意义下，其中$P$是一个大质数。在程序实现中，取$P = 998244353$。

加法/减法

给定多项式$A(x),B(x)$，求$A(x) + B(x)$或$A(x) - B(x)$。

将多项式的对应项直接相加减即可。时间复杂度$O(n)$。

乘法

给定多项式$A(x),B(x)$，求$A(x)B(x)$。

对于普通的多项式乘法，可以用经典的FFT或分治乘法实现。在模特殊的大质数$P$时可以使用NTT，一般要求$P = c \cdot 2 ^ k + 1$，如UOJ模数$998244353 = 7 \times 17 \times 2 ^ {23} + 1$。时间复杂度$O(n \log n)$。

求导/积分

给定多项式$A(x)$，求$A'(x)$或$\int_{0} ^ {\infty} {A(x)}$。

根据定义逐项求导/积分即可，具体过程见微积分基本定理。时间复杂度$O(n)$。

多项式的一些比较正常的运算就到此结束了。接下来是一些有趣的姿势。

逆元

给定多项式$A(x)$，求$A^{-1}(x) \pmod {x ^ n}$。

$A^{-1}(x)$称为$A(x)$的逆元，满足$A(x)A^{-1}(x) \equiv 1 \pmod {x ^ n}$。

首先考虑$A^{-1}(x) \pmod {x}$，显然有$A^{-1}(x) \equiv a_0 \pmod {x}$。

考虑倍增。如果我们知道了$A^{-1}(x) \pmod {x ^ k}$，怎样得到$A^{-1}(x) \pmod {x ^ {2k}}$呢？

设$B(x) = A^{-1}(x) \pmod {x ^ k},C(x) = A^{-1}(x) \pmod {x ^ {2k}}$，显然有

$$A(x)B(x) \equiv 1 \pmod {x ^ k} \\ A(x)C(x) \equiv 1 \pmod {x ^ k}$$

则有

$$B(x) - C(x) \equiv 0 \pmod {x ^ k}$$

可以推得

$$(B(x) - C(x)) ^ 2 = B^2(x) - 2B(x)C(x) + C^2(x) \equiv 0 \pmod {x ^ {2k}} \Rightarrow \\ C(x) \equiv 2B(x) + A(x)B^2(x) \pmod {x ^ {2k}}$$

上述过程可以用FFT或NTT实现。如此，就可以在$O(\log n)$次迭代后求出多项式的逆元。根据主定理有

$$T(n) = T(n/2) + O(n \log n) = O(n \log n)$$

于是时间复杂度是$O(n \log n)$。在此膜拜一下Miskcoo神犇的Blog。

除法/模

给定$n$次多项式$A(x)$，$m$次多项式$B(x)$，求$\frac{A(x)} {B(x)}$。

//似乎没有这么简单....我重更一下。

题目所求即为$A(x) B^{-1}(x)$，我们只需要求$B(x)$的逆元即可。时间复杂度$O(n \log n)$。

对数

给定多项式$A(x)$，求$\ln(A(x))$。

设$B(x) = \ln(A(x))$，根据链式法则有

$$B'(x) = (\ln(A(x))' = \ln'(A(x))A'(x) = \frac{A'(x)} {A(x)}$$

于是只需要求一次$A(x)$的逆元，与$A'(x)$相乘得到$B'(x)$，再积分还原$B(x)$即可。时间复杂度$O(n \log n)$。

注意，在求对数时，必须保证$a_0 = 1$。

指数

给定多项式$A(x)$，求$e ^ {A(x)}$，即$\exp(A(x))$。

设$f(x) = e ^ {A(x)}$。根据定义，可以列出方程$g(f(x)) = \ln(f(x)) - A(x) = 0$。

考虑牛顿迭代法。首先，易知$f(x) = e ^ {A(x)} \equiv 1 \pmod {x}$。

接下来我们考虑怎样由$f_0(x) \pmod {x ^ k}$推出$f(x) \pmod {x ^ {2k}}$。

显然有$f_0(x) \equiv f(x) \pmod {x ^ k}$。在$f_0(x)$处泰勒展开，可得

$$\begin{aligned} g(f(x)) &= 0 \\ &= g(f_0(x)) + g'(f_0(x))(f(x) - f_0(x)) + g''(f_0(x))(f(x) - f_0(x)) ^ 2 + ... \\ &= g(f_0(x)) + g'(f_0(x))(f(x) - f_0(x)) \pmod {x ^ {2k}} \end{aligned}$$

则有

$$f(x) = f_0(x) - \frac {g(f_0(x))} {g'(f_0(x))} \pmod {x ^ {2k}}$$

注意到泰勒展开时，由于$f(x) - f_0(x) \equiv 0 \pmod {x ^ {sk}} \; (s \ge 2)$，大于等于二次的项均可以被消去，于是剩下的式子就十分简洁明了。将方程$g(f(x)) = \ln(f(x)) - A(x)$代入上式，得

$$\begin{aligned} f(x) &= f_0(x) - \frac{\ln(f_0(x)) - A(x)} {\frac{1} {f_0(x)}} \\ &= f_0(x)(1 - \ln(f_0(x)) + A(x)) \pmod {x ^ {2k}} \end{aligned}$$

根据主定理有$T(n) = T(n/2) + O(n \log n) = O(n \log n)$，于是时间复杂度$O(n \log n)$。

乘方

给定多项式$A(x)$，求$A(x) ^ k$的前$n$次项。

方法1：快速幂

考虑像一般整数的快速幂一样，每一轮迭代FFT一次并舍去多余项。时间复杂度$O(n \log n \log k)$。

方法2：指对变换

由指数函数和对数函数的性质，有

$$A(x) ^ k = e ^ {k \ln A(x)}$$

于是时间复杂度就是$O(n \log n)$。注意，在这种方法中，由于需要对多项式求对数，则须$a_0 = 1$。若$a_0 \neq 1$怎么办呢？我们可以稍微转化一下。设$A(x)$的最低次项为$a_d x ^ d$，则有

$$A(x) ^ k = a_d x ^ {kd} (\frac{A(x)} {a_d x ^ d}) ^ k$$

此时括号内的式子一定满足$a_0 = 1$，满足对数运算条件。

开方

给定多项式$A(x)$，求$\sqrt[k]{A(x)}$。

类似乘方运算的方法2，我们有

$$\sqrt[k]{A(x)} = A(x) ^ {\frac{1} {k}} = e ^ {\frac{\ln A(x)} {k}}$$

时间复杂度同样是$O(n \log n)$。对于常数项不为1的情况，同样有

$$A(x) ^ {\frac{1} {k}} = a_d x ^ {\frac{d}{k}} (\frac{A(x)} {a_d x ^ d}) ^ {\frac{1} {k}}$$

注意到必须满足$d | k$才可以。

文中许多思路和推导过程摘自JCVB的论文《生成函数的运算和组合计数问题》。