「学习笔记」多项式算法

前言

在 OI 中，许多涉及到生成函数的计数题都需要使用一些多项式算法，所以掌握多项式算法是必要的。

常见导数

$$\begin {split}(x^n)' & = nx^{n - 1} \\(e^x)' & = e^x \\(a^x)' & = e^{x \ln a} \ln a \\(\ln x)' & = x^{-1}\end {split}$$

多项式加减法

加减法只要对应系数加减即可，这是线性的。

多项式乘法

乘法可以使用 FFT 完成。假设要计算 $H(x) = F(x) G(x)$，那么只需要把 $F(x), G(x)$ 进行 DFT，然后对应点值相乘后再 IDFT 回去就行了，时间复杂度 $O(n \log n)$。

多项式求导与积分

对于多项式 $F(x) = \sum_{i = 0}^{n} a_i x^i$，我们有：

$$F'(x) = \sum_{i = 0}^{n - 1} a_{i + 1} (i + 1)x^i \\\int F(x) \text{d}x = \sum_{i = 1}^{n + 1} \frac{a_{i - 1}}{i} x^i$$

可以直接线性计算。

泰勒展开

泰勒展开是多项式牛顿迭代的前置技能，它的思想就是用多项式来逼近一个函数。定义函数 $f(x)$ 在点 $x_0$ 的泰勒展开为：

$$f(x) = \sum_{i = 0}^{\infty} \frac{f^{(i)}(x_0)}{i!} (x - x_0)^i$$

其中 $f^{(i)}(x)$ 表示函数 $f(x)$ 的 $i$ 阶导数。 当然 $f(x)$ 不仅可以以数为参数，也可以以函数为参数。

多项式牛顿迭代

多项式牛顿迭代可以解决多项式求逆和多项式开根，它也是多项式指数函数的前置技能之一。

问题：给定 $G(x)$，构造 $F(x)$，满足 $G(F(x)) \equiv 0 \pmod {x^n}$。

假设我们已经构造出了 $F_0(x)$ 满足 $G(F_0(x)) \equiv 0 \pmod{x^{\lceil \frac{n}{2} \rceil}}$，现在我们要求出 $F(x)$。考虑 $G(F(x))$ 在 $F_0(x)$ 上的泰勒展开：

$$\begin {split}G(F(x)) & = G(F_0(x)) & \\& + \frac{G'(F_0(x))}{1!} & (F(x) - F_0(x)) \\& + \frac{G''(F_0(x))}{2!}& (F(x) - F_0(x))^2 \\& & \vdots\end {split}$$

发现 $F(x)$ 和 $F_0(x)$ 的前 $\lceil \frac{n}{2} \rceil$ 项应该是一样的，所以我们就有：

$$G(F(x)) = G(F_0(x)) + G'(F_0(x)) (F(x) - F_0(x)) \\G'(F_0(x)) F(x) \equiv G'(F_0(x)) F_0(x) - G(F_0(x)) \pmod{x^n} \\F(x) \equiv F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} \pmod{x^n} \\$$

所以就可以递归了，如果一次递归可以做到 $O(n \log n)$ 那么时间复杂度就是 $T(n) = T(\frac{n}{2}) + O(n \log n) = O(n \log n)$。

多项式求逆

问题：给定 $H(x)$，求 $F(x) H(x) \equiv 1 \pmod {x^n}$。

考虑令 $G(F(x)) = F^{-1}(x) - H(x)$，并使用牛顿迭代法。那么我们有：

$$\begin {split}F(x) & \equiv F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} \pmod {x^n} \\& \equiv F_0(x) - \frac{F_0^{-1}(x) - H(x)}{-F_0^{-2}(x)} \\& \equiv F_0(x) - \frac{F_0^{-1}(x) - H(x)}{-F_0^{-2}(x)} \\& \equiv 2F_0(x) - H(x)F_0^2(x)\end {split}$$

对于 $n = 1$ 可以直接求逆元，总时间复杂度 $O(n \log n)$。

多项式开方

问题：给定 $H(x)$，求 $F(x)$ 满足 $F^2(x) \equiv H(x) \pmod{x^n}$。

考虑令 $G(F(x)) = F^{2}(x) - H(x)$，并使用牛顿迭代法。那么我们有：

$$\begin {split}F(x) & \equiv F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} \pmod{x^n} \\& \equiv F_0(x) - \frac{F_0^{2}(x) - H(x)}{2F_0(x)} \\& \equiv \frac{F_0^{2}(x) + H(x)}{2F_0(x)} \\\end {split}$$

对于 $n = 1$ 需要用到二次剩余，总复杂度 $O(n \log n)$。

多项式对数函数

已知 $F(x)$，我们要求 $\ln F(x)$。

考虑 $\ln$ 的意义。我们有 $(\ln x)’ = x^{-1}$，我们将 $x^{-1}$ 展开：

$$x^{-1} = (1 - (1 - x))^{-1} = \sum_{i = 0}^{\infty} (1 - x)^i$$

那么有 $(\ln x)’ = \sum_{i = 0}^{\infty} (1 - x)^i$，两边同时积分得到：

$$\ln x = \sum_{i = 1}^{\infty} \frac{(1 - x)^i}{i}$$

那么多项式的 $F(x)$ 的 $\ln$ 就是：

$$\ln F(x) = \sum_{i = 1}^{\infty} \frac{(1 - F(x))^i}{i}$$

注意 $F(x)$ 的常数项必须为 $1$。怎么求 $\ln F(x) \pmod{x^n}$ 呢？考虑复合函数求导：

$$(\ln F(x))' = \frac{\text{d} \ln F(x)}{\text{d}x} = \frac{\text{d} \ln F(x)}{\text{d} F(x)} \cdot \frac{\text{d} F(x)}{\text{d}x} = \frac{F'(x)}{F(x)}$$

两边同时积分得到：

$$\ln F(x) = \int \frac{F'(x)}{F(x)} \text{d} x$$

那么使用多项式求逆计算即可，时间复杂度 $O(n \log n)$。

多项式指数函数

问题：给定 $H(x)$，求 $F(x) = \exp(H(x)) \pmod{x^n}$。

考虑令 $G(F(x)) = \ln F(x) - H(x)$，并使用牛顿迭代法。那么我们有：

$$\begin {split}F(x) & \equiv F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} \pmod{x^n} \\& \equiv F_0(x) - \frac{\ln F_0(x) - H(x)}{F_0^{-1}(x)} \\& \equiv F_0(x)(1 - \ln F_0(x) + H(x)) \\\end {split}$$

$n = 1$ 时 $H(x)$ 必须是 $0$，此时 $F(x) = 1$，总复杂度 $O(n \log n)$。

代码实现

//「Luogu 5245」Polynomial Power