约定
设 $F\left[i\right]$ 表示 $x_i$ 的系数。
四则运算
加减法
$$ F \left(x\right) \pm G\left(x\right) = \sum\limits_{i = 0}\left(F\left[i\right] \pm g\left[i\right]\right) x^i $$
就是对应项做对应运算。
乘法不必多说
除法
$$F\left(x\right) / G\left(x\right) = F\left(x\right) G\left(x\right)^{-1}$$
其中 $G\left(x\right)^{-1}$ 定义为 $G\left(x\right)$ 的“乘法逆”。
乘法逆
若
$$F\left(x\right) G\left(x\right) = 1$$
那么把 $G\left(x\right)$ 称为 $F\left(x\right)$ 的乘法逆。
求解
若当前多项式只有常数项，那么直接求该数的逆元即可。
然后我们通过倍增的方法来求解。
设我们已经得到了 $R_*\left(x\right) = F\left(x\right)^{-1} \pmod{x^{n / 2}}$。
再设 $R\left(x\right) = F\left(x\right)^{-1} \pmod{x^n}$。
有 $R\left(x\right) = R_*\left(x\right) \pmod{x^{n / 2}}$
我们平方一下：
$$\left(R\left(x\right) - R_*\left(x\right)\right)^2 = 0 \pmod{x^n}$$
然后展开：
$$R\left(x\right)^2 - 2R\left(x\right)R_*\left(x\right) + R_*\left(x\right)^2 = 0 \pmod{x^n}$$
然后乘上 $F\left(x\right)$：
$$R\left(x\right) - 2R_*\left(x\right) + R_*\left(x\right)^2F\left(x\right) = 0 \pmod{x^n}$$
于是我们得到了 $R\left(x\right) \pmod{x^n}$ 的求法。
复杂度为 $\tilde{\mathcal O} \left(n\right)$
带余除法
我们用 $F^T\left(x\right)$ 表示将 $F\left(x\right)$ 的系数翻转后的多项式（例如 $3x^2 + 2x + 1$ 变为 $x^2 + 2x + 3$），实际上 $F^T\left(x\right) = x^nF\left(x^{-1}\right)$。
给出 $F\left(x\right)$ 和 $G\left(x\right)$，我们现在要求满足 $F\left(x\right) = Q\left(x\right)G\left(x\right) + R\left(x\right)$ 的 $Q\left(x\right)$ 和 $R\left(x\right)$。
首先换元：
$$F\left(x^{-1}\right) = Q\left(x^{-1}\right)G\left(x^{-1}\right) + R\left(x^{-1}\right)$$
然后翻转系数：
$$F^T\left(x\right) / x^n = Q^T\left(x\right) / x^n \times G^T\left(x\right) / x^n + R\left(x\right) / x^{m - 1}$$
然后乘上 $x^n$：
$$F^T\left(x\right) = Q^T\left(x\right) \times G^T\left(x\right) + R\left(x\right) / x^{n - m + 1}$$
对 $x^{n - m + 1}$ 取模：
$$F^T\left(x\right) = Q^T\left(x\right) \times G^T\left(x\right) \pmod{x^{n - m + 1}}$$
这时容易算出 $Q\left(x\right)$。然后 $R\left(x\right) = F\left(x\right) - Q\left(x\right) G\left(x\right)$。
复合
$F\left(x\right)$ 与 $G\left(x\right)$ 的复合定义为：
$$F\left(G\left(x\right)\right) = \sum\limits_{i = 0} F\left[i\right] G\left(x\right)^i$$
求导
多项式求导的定义是经典的。
$F'\left(x\right) = \sum\limits_{i = 0} F\left[i\right]ix^{i - 1}$
在线性时间内完成计算。
积分
多项式积分的定义也是经典的。
$F'\left(x\right) = C + \sum\limits_{i = 0} F\left[i\right]x^{i + 1} / i$
在线性时间内完成计算。
牛顿（Newton）迭代
牛顿迭代用于求解满足 $G\left(F\left(x\right)\right) = 0$ 的 $F\left(x\right) \pmod {x^n}$，其中 $G\left(x\right)$ 是给定的。
牛顿迭代公式为：
$$F\left(x\right) = F_*\left(x\right) - \frac{G\left(F_*\left(x\right)\right)}{G'\left(F_*\left(x\right)\right)}$$
我们依然使用倍增求解。
开方
使用牛顿迭代找解即可。
自然对数 $\ln$
多项式 $\ln$ 由麦克劳林级数（即在 $x = 0$ 处展开的泰勒级数）定义：
$$\ln\left(F\left(x\right)\right) = -\sum\limits_{i = 1}\frac{\left(1 - F\left(x\right)\right)^i}i$$
设 $\ln\left(F\left(x\right)\right) = G\left(x\right)$，两边同时求导：
$$\ln'\left(F\left(x\right)\right) \times F'\left(x\right) = G'\left(x\right)$$
而 $\ln\left(x\right) = \frac1x$，于是：
$$G'\left(x\right) = \frac{F'\left(x\right)}{F\left(x\right)}$$
$$G\left(x\right) = \int\left(F'\left(x\right) / F\left(x\right)\right)$$
自然指数 $\exp$
$\exp$ 是 $\ln$ 的逆运算，于是可以牛顿迭代暴力搞。注意必须保证 $F\left[0\right] = 0$。
快速幂
$$F^k\left(x\right) = e^{k \cdot \ln\left(F\left(x\right)\right)}$$
常数比较大。
这种方式需要保证 $F\left[0\right] = 1$，如果没有这个怎么做？
我们把 $F\left(x\right)$ 写成 $G\left(x\right) * cx^p$ 的形式，满足 $G\left[0\right] = 1$。这样的 $c$ 和 $p$ 一定存在，比如取 $c$ 为 $F\left(x\right)$ 的最低非空项系数，而 $p$ 就是$F\left(x\right)$ 的末尾非空项个数。
于是 $F^k\left(x\right) = \left(G\left(x\right) \cdot cx^p\right)^k = G^k\left(x\right) \cdot c^kx^{pk}$
代码
不着急。