暴力多项式操作

引言

本文将介绍如何 $O(n^2)$ 计算多项式求逆、取 $\exp$、取 $\ln$。

Q：为什么不用基于 FFT / NTT 的 $O(n\log n)$ 方法？

A：

• 自从快速傅里叶变换（FFT）在 NOI 大纲中被定为 $10$ 级（相当于移除考纲）后，多项式技术开始式微，大多数生成函数问题不需要优化到 $O(n\cdot \mathrm{polylog}(n))$，而只需要做到 $O(n^2)$。因此没有必要记忆复杂的线性对数算法。
• 我们有时会对很小的多项式进行非常多次的操作（例如集合幂级数），此时 $O(n^2)$ 的方法无论是实现难度还是速度都远远胜过 $O(n\log n)$ 的方法。
• 题目给出的模数可能无法支持 NTT 操作。

为了方便，令 $F_i=[z^i]F(z)$。

复合函数求导法则

由于这玩意我总是忘记，所以记一下，后面会用到：

$$(f(g(z)))' = f'(g(z)) \cdot g'(z)$$

多项式求逆

给定多项式 $F(z)$，令 $G(z)=\frac{1}{F(z)}$，求 $G(z)\bmod x^n$。保证 $F_0 \neq 0$。

根据定义有：

$$[z^k](F(z)\cdot G(z)) = \sum_{i=0}^{k} F_iG_{k-i} = [k=0]$$

当 $k=0$ 时 $F_0G_0=1\implies G_0=F_0^{-1}$。因此接下来可令 $k>0$：

$$\begin{aligned} &\sum_{i=0}^{k} F_iG_{k-i} = 0\\ &\implies-F_0G_k = \sum_{i=1}^{k} F_iG_{k-i}\\ &\implies G_k = -\frac{1}{F_0}\sum_{i=1}^{k} F_iG_{k-i} \end{aligned}$$

可以直接递推，时间复杂度为 $O(n^2)$。

多项式 exp

给定多项式 $F(z)$，令 $G(z)=\exp F(z)$，求 $G(z)\bmod x^n$。保证 $F_0=0$。

根据定义有：

$$\begin{aligned} &G'(z) = \exp(F(z))\cdot F'(z) = G(z)\cdot F'(z)\\ &\implies [z^k]G'(z) = (k+1)G_{k+1} = \sum_{i=0}^{k} [z^i]F'(z)\cdot G_{k-i} = \sum_{i=0}^{k} (i+1)F_{i+1}G_{k-i}\\ &\implies G_{k} = \frac{1}{k} \sum_{i=0}^{k-1} G_{k-1-i} F_{i+1} (i+1) = \frac{1}{k} \sum_{i=1}^{k} G_{k-i} F_{i} i \end{aligned}$$

边界 $G_0=0$。可以直接递推，时间复杂度为 $O(n^2)$。

多项式 ln

给定多项式 $F(z)$，令 $G(z)=\ln F(z)$，求 $G(z)\bmod x^n$。保证 $F_0=1$。

有两种做法。

法 1：求导法

根据定义有：

$$\begin{aligned} &G'(z) = (\ln F(z))' = \frac{1}{F(z)}\cdot F'(z)\\ &\implies G(z) = \int \frac{1}{F(z)}\cdot F'(z) \mathrm{d}z \end{aligned}$$

多项式求导和多项式积分是容易的，复杂度瓶颈在多项式求逆和多项式乘法。我们全部用 $O(n^2)$ 的算法就可以做到 $O(n^2)$。

这个方法易于理解但常数较大。

法 2：递推法

根据定义有：

$$\begin{aligned} &G'(z) = \frac{1}{F(z)}\cdot F'(z)\\ &\implies F'(z) - F(z)G'(z) = 0\\ &\implies [z^k] F'(z) = (k+1)F_{k+1} = \sum_{i=0}^{k} F_{k-i} (i+1) G_{i+1}\\ &\implies F_{k+1} = \frac{1}{k+1} \sum_{i=0}^{k} F_{k-i} (i+1) G_{i+1} \implies F_k = \frac{1}{k}\sum_{i=0}^{k-1} F_{k-i-1} (i+1) G_{i+1}\\ &\implies F_k = \frac{1}{k}\sum_{i=1}^{k} F_{k-i} i G_{i} = \frac{1}{k}\sum_{i=1}^{k-1}F_{k-i} i G_{i} + G_k\\ &\implies G_k = F_k - \frac{1}{k}\sum_{i=1}^{k-1} F_{k-i} i G_{i} \end{aligned}$$

边界 $G_0=0$。可以直接递推，时间复杂度为 $O(n^2)$。

多项式开根

给定多项式 $F(z)$，令 $G(z)=\sqrt{F(z)}$，求 $G(z)\bmod x^n$。保证 $F_0\neq 0$。

法 1：对数法

$$G(z)=\sqrt{F(z)}=\exp \ln \sqrt{F(z)} = \exp \frac{1}{2}\ln F(z)$$

只需要一次 $\ln$ + 一次 $\exp$ 就可以计算，需要适当调整以满足常数项限制。

时间复杂度为 $O(n^2)$，常数较大。

法 2：递推法

根据定义有（显然有边界 $G_0=\sqrt{F_0}$）：

$$\begin{aligned} &G^2(z) = F(z)\\ &\implies F_k = \sum_{i=0}^{k} G_iG_{k-i} = 2\sqrt{F_0}G_k + \sum_{i=1}^{k-1} G_iG_{k-i}\\ &\implies G_k = \frac{F_k}{2 \sqrt{F_0}}-\frac{1}{2 \sqrt{F_0}} \sum_{i=1}^{k-1} G_iG_{k-i} \end{aligned}$$

可以直接递推，时间复杂度为 $O(n^2)$。

总结

操作	递推公式	边界	隐含限制
求逆	$G_k=-\frac{1}{F_0}\sum_{i=1}^{k} F_iG_{k-i}$	$G_0=\frac{1}{F_0}$	$F_0\neq 0$
$\exp$	$G_k=\frac{1}{k} \sum_{i=1}^{k} G_{k-i} F_{i} i$	$G_0=1$	$F_0=0$
$\ln$	$G_k=F_k - \frac{1}{k}\sum_{i=1}^{k-1} F_{k-i} i G_{i}$	$G_0=0$	$F_0=1$
开根	$G_k = \frac{F_k}{2 \sqrt{F_0}}-\frac{1}{2 \sqrt{F_0}} \sum_{i=1}^{k-1} G_iG_{k-i}$	$G_0=\sqrt{F_0}$	$F_0\neq 0$