#多项式操作汇总
最近学了不少多项式的小 trick，感觉不记一下容易忘。那我就把做法都摆在这里吧，代码还是自己去写了。（鉴于所有操作都是建立在 FFT 之上的，所以会写 FFT 的话所有东西的代码都能写出来了）
##多项式乘法
这个就是一切的基础，先把这个代码搞熟后面就都能写啦。
##多项式逆元
定义多项式 $g(x)$ 的逆元 $g^{-1}(x)$（以下为了方便简记为 $f(x)$）是满足如下等式的多项式：
$$ \begin{matrix} g(x) \cdot f(x) \equiv 1 & (\mod x^n) \end{matrix} $$
可以想象，模 $x^n$ 的意思就是把 $x^{n+1}$ 及更高的项都删掉，剩下的部分。为什么我们可以这样做呢？因为在解决实际问题的时候我们都只关心前 $n$ 项（即 $x^0 \sim x^{n-1}$ 的系数）。
求 $f(x)$ 的方法可能不止一种，但是我觉得用泰勒展开这个方法虽然麻烦但是好记（因为大多数问题可以用它——它是“通解”）。
注意：以下多项式都会在第一次用 $f(x)$ 表示过后就可能省掉后面的 $(x)$，你需要知道它是一个多项式。
我们先构造一个函数 $H(f) = f^{-1} - g$。你没有看错，这个 $H(f)$ 函数的自变量就是一个多项式。为什么要这样构造函数呢？因为可以发现当自变量 $f = g^{-1}$，即 $f$ 就是答案的时候，$H(f) = 0$。
我们用倍增的方法求这个 $f$，假设已经求出 $f_0(x)$ 是 $f$ 前 $\lceil \frac{n}{2} \rceil$ 项，即
$$ \begin{matrix} f_0 \equiv f & (\mod x^{\lceil \frac{n}{2} \rceil}) \end{matrix} $$
现在我们要用 $f_0$ 和 $g$ 表示出 $f$。利用我们刚才构造的函数，根据 $f_0$ 的定义有
$$ \begin{matrix} H(f_0) \equiv 0 & (\mod x^{\lceil \frac{n}{2} \rceil}) \end{matrix} $$
为了实现上面黑体字的目的，我们对 $H(f)$ 在 $f_0$ 处进行泰勒展开（想点进去看的请翻到文章末尾），即用下面这个式子去逼近 $H(f)$
$$ H(f) = \sum_ {i = 0}^{+ \infty} { \frac{H^{[i]}(f_0) (f-f_0)^i}{i!} } $$
注意上面这个等式不是模意义下的，不需要取模它们就相等。
接下来我们观察一下 $(f-f_0)^i$，由于 $f - f_0 \equiv 0 (\mod x^{\lceil \frac{n}{2} \rceil})$，发现当 $i = 2$ 时，最高次项平方之后次数一定 $\ge n$，所以有 $\forall i > 1, (f-f_0)^i \equiv 0 (\mod x^n)$，那么上面的泰勒展开的无穷多项就只剩了两项，整理出来就是
$$ \begin{matrix} H(f) \equiv H(f_0) + H'(f_0)(f - f_0) & (\mod x^n) \\ \because H(f) \equiv 0 & (\mod x^n) \\ \therefore H(f_0) + H'(f_0)(f - f_0) \equiv 0 & (\mod x^n) \end{matrix} $$
移项得到
$$ \begin{matrix} f \equiv f_0 - \frac{H(f_0)}{H'(f_0)} & (\mod x^n) \end{matrix} $$
至此我们得到了牛顿迭代的公式，以后可以记它，就不用每次都泰勒展开了。接下来的工作就是把刚才构造的 $H(f)$ 带进去。
$$ \begin{matrix} f \equiv 2f_0 - gf_0 & (\mod x^n) \end{matrix} $$
递归下去，再用这个式子回溯，就求出来啦！
时间复杂度：$T(n) = T(\frac{n}{2}) + O(n\log n) = O(n\log n)$，发现这个小秘密后，我们可以无限套，理论复杂度不变
##多项式除法 & 取模
注意这里的除法不是在模意义下的！所以它会有商和余数，即如果我要求 $\frac{A(x)}{B(x)}$，我就是要求两个多项式 $D(x)$ 和 $R(x)$，使得它们满足下面这样一个等式
$$ A(x) = B(x)D(x) + R(x) $$
现在我们记 $n$ 为 $A$ 的次数，$m$ 为 $B$ 的次数，那么有 $D$ 的次数为 $\mathrm{max}(n - m, 0)$，$R$ 的次数 $\le m - 1$。
记 $F(x)$ 的次数为 $t$， $F^R(x) = F(\frac{1}{x}) \cdot x^t$，直观理解就是把 $F$ 的系数反转一下。
接下来将 $\frac{1}{x}$ 带入到原式中，再两边同乘 $x^n$，看看会发生什么
$$ x^nA(\frac{1}{x}) = x^{m}B(\frac{1}{x}) \cdot x^{n-m}D(\frac{1}{x}) + x^{n-m+1} \cdot x^{m-1}R(\frac{1}{x}) \\ \therefore A^R(x) = B^R(x)D^R(x) + x^{n-m+1}R^R(x) $$
如果我们将新的等式放在模 $x^{n-m+1}$ 的意义下，$R(x)$ 就被消掉了！与此同时 $D^R(x)$ 最高次为 $x^{n-m}$，故不会受到任何影响，即模意义下求出的 $D^R(x)$ 与非模意义下的完全相同。
$$ \begin{matrix} A^R(x) \equiv B^R(x)D^R(x) & (\mod x^{n-m+1}) \\ \therefore D^R(x) \equiv A^R(x)[B^R(x)]^{-1} & (\mod x^{n-m+1}) \end{matrix} $$
$D(x)$ 就是 $D^R(x)$ 反转一下系数，把 $D(x)$ 代到最初的式子里就能得到 $R(x)$ 了。
###多项式多点求值
任务：给出多项式 $F(x)$ 和集合 ${ x_1, x_2, \cdots , x_n }$，要求返回一个集合 ${ F(x_1), F(x_2), \cdots , F(x_n) }$。
构造多项式 $A(x) = (x - x_1)(x - x_2)\cdots(x - x_n)$，令 $G(x) \equiv F(x) (\mod A(x))$，那么对于 $\forall i \in [1, n], G(x_i) = F(x_i)$。
为什么呢？因为
$$ F(x) = A(x)D(x) + G(x) $$
而 $\forall i \in [1, n], A(x_i) = 0, \therefore F(x_i) = G(x_i)$。
于是就可以分治了。令 $A_l(x) = \prod_{i = 1}^{\lfloor \frac{n}{2} \rfloor} { (x - x_i) }, A_r(x) = \prod_{i = \lfloor \frac{n}{2} \rfloor + 1}^n { (x - x_i) }$，然后把 $F(x)\ \mod A_l(x)$ 和 $F(x)\ \mod A_r(x)$ 扔下去递归了。
时间复杂度：$O(n \log^2 n)$
##多项式 ln & exp
应该有不少人好奇这两个操作的组合意义是什么。事实上这个问题我并不是很清楚，我们也许可以通过泰勒展开后的系数研究一下它的组合意义，但它们的价值主要不在于组合意义，而在于其他方面的应用。
具体应用在讲完做法后立刻就会有一个，所以不必着急，我们先看看多项式取 ln 怎么求。
###多项式取 ln
注意到这样一个等式
$$ (\ln f(x))' = \frac{f'(x)}{f(x)} $$
于是积分一下就可以轻易地求出 $\ln f(x)$ 了
$$ \ln f(x) = \int \frac{f'(x)}{f(x)} $$
其中，求导和积分都能在 $O(n)$ 时间内求出，所以总时间复杂度 $O(n)$。
细心的读者一定会问：积分之后，常数项如何确定？注意到这里的 $[x^0]f(x)$ 必须为 $1$，也就是说 $[x^0] \ln f(x)$ 一定是 $0$，那么积分完后常数项为 $0$ 就好了。（如果 $[x^0]f(x) \ne 1$ 怎么求？QAQ 我也不会，因为我们似乎很难找到 $\ln c (c > 0)$ 在剩余系下的表示……）
###多项式求 exp
我们要求这样的一个函数 $f(x)$，满足
\begin{matrix} f(x) \equiv e^{g(x)} & (\mod x^n) \end{matrix}
两边取对数，我们有
\begin{matrix} \ln f(x) \equiv g(x) & (\mod x^n) \end{matrix}
我们还是考虑倍增求 $f$，套用上面泰勒展开推出来的结果，构造函数 $H(f) = \ln f - g$，令 $f_0 \equiv f (\mod x^{\lceil \frac{n}{2} \rceil})$，于是得到
\begin{matrix} f \equiv f_0 - \frac{\ln f_0 - g}{f_0^{-1}} & (\mod x^n) \\ f \equiv f_0(1 - \ln f_0 + g) & (\mod x^n) \end{matrix}
这样就 $O(n \log n)$ 解决啦，你会发现求 exp 其实依赖于求 ln。同样地我们只能求 $[x^0]g(x) = 0$ 的 $e^{g(x)}$。
接下来就是一个经典的应用。
###多项式乘方
求 $f(x)$ 满足
\begin{matrix} f(x) \equiv g(x) ^ k & (\mod x^n) \end{matrix}
指数相关，考虑两边取对数
\begin{matrix} \ln f(x) \equiv k \ln g(x) & (\mod x^n) \\ f(x) = e^{k \ln g(x)} & (\mod x^n) \end{matrix}
这就解决了？别忘了常数项的问题，问题有两个：
- $[x^0]g(x) > 1$，我们可以将常数项提出来，得到 $g'(x)$（注意不是导数，这个就是 $g(x)$ 的每项乘上常数项的逆元），那么问题变成了求 $(g'(x))^k c^k$，$c$ 代表常数项，就是在上面的过程进行完后每项乘上 $c^k$ 即可；
- $[x^0]g(x) = 0$，先位移到常数项不为 $0$，即得到 $g'(x) = \frac{g(x)}{x^d}$，$d$ 表示前缀连续 $0$ 的个数，那么问题变成了求 $(g'(x))^k x^{kd}$，就是上面的过程进行完后再位移 $kd$ 位即可。
至此多项式乘方就完整地解决了。
