第二次学了，上次的文章在这里：生成函数与组合计数

先粘一下以防以后忘了：

这次会以 $F(z),x$ 作为形式幂级数，也就是说后文的 $x,x_0,\dots$ 都是形式幂级数。

前置芝士：泰勒展开，在上次的文章中可以看到。

牛顿迭代

$$F(G(z)) = 0$$

求 $G(z) \bmod z^n$

设 $x_0 = x\bmod z^n$ ，考虑求 $x \bmod z^{2n}$ 。

我们将 $F(x)$ 在 $x_0$ 处展开，那么有

$$F(x) = F(x_0) + F'(x-x_0) + F''(x_0) \frac{(x-x_0)^2}{2} + \dots \pmod{z^{2n}}$$

观察这个式子，由于 $x - x_0 = 0 \pmod {z^n}$ 即 $(x - x_0)^2 = 0 \pmod {z^{2n}}$ ，也就是说从第三项开始后面都爆零了。

那么有

$$F(x) = 0 = F(x_0) + F'(x-x_0)\\ x = x_0 - \frac{F(x_0)}{F'(x_0)}$$

倍增即可求出 $x$。

多项式求逆

以前是直接推的，这次用牛顿迭代来推求逆。

$$F(z)G(z) \equiv 1 \pmod{z^n}$$

考虑设 $P(x) = \frac{1}{x} - F(z)$ ，注意这里 $F(z)$ 是一个常数。于是我们即是求 $P(x) = 0$ 的解。

直接套用前面的结论，有

$$\begin{aligned} x &= x_0 - \frac{F(x_0)}{F'(x_0)}\\ x &= x_0 - \frac{\frac 1 {x_0} - F(z)}{-\frac{1}{x_0^2}}\\ x &= x_0(2 - x_0F(z)) \end{aligned}$$

倍增求出 $x$ 即可。

多项式取模

求 $A(z) \bmod B(z)$

简单的想法：直接用小学学过的大除法，复杂度是 $O(n(n-m))$ 的。但是注意，如果用大除法来做多项式 $\gcd$ 的话可以分析出复杂度为 $O(nm)$ 。

考虑如何快速求。我们设 反转变换 是 $F^R(z) = z^{\deg(F(z))} F(\frac 1 z)$ ，其中 $\deg(x)$ 表示 $x$ 的最高次项的次数。直观的理解就是把多项式的系数倒过来。

设 $\deg(A(z)) = n , \deg(B(z)) = m$ ，考虑带余除法的过程

$$A(z) = B(z)F(z) + G(z)$$

其中 $F(z)$ 是商（次数必然是 $n - m$），$G(z)$ 是余式（次数小于 $m$）

对两边分别进行反转变换

$$\begin{aligned} z^nA(\frac 1 z) &= z^n( B(\frac 1 z)F(\frac 1 z) + G(\frac 1 z))\\ A^R(z) &= z^mB(\frac 1 z) z^{n-m} F(\frac 1 z) + z^n G(\frac 1 z)\\ A^R(z) &= B^R(z)F^R(z) + z^{n-\deg(G(z))} G^R(z) \end{aligned}$$

我们考虑它两边 $\bmod z^{n-m+1}$ 后得到的东西，最后那项爆零了

$$F^R(z) = A^R(z) (B^R(z))^{-1}\bmod z^{n-m+1}$$

我们知道 $F(z)$ 的次数只有 $n-m$ ，我们相当于算出了准确的 $F(z)$ ，于是可以轻松算出 $G(x)$ 了。

只有求逆操作，复杂度是 $O(n\log n)$。

多项式对数

考虑求

$$G(z) = \ln F(z)$$

导一下：

$$G'(z) = \frac{1}{F(z)} F'(z)$$

乘起来再积回去即可。

多项式指数

然后考虑求

$$G(z) = \exp F(z)\\$$

类似求逆的想法，构造

$$P(x) = \ln x - F(z)$$

同样的，应用牛顿迭代

$$\begin{aligned} x &= x_0 - \frac{F(x_0)}{F'(x_0)}\\ x &= x_0 - \frac{\ln {x_0} - F(z)}{\frac{1}{x_0}}\\ x &= x_0(1 - \ln x_0 - F(z)) \end{aligned}$$

同样倍增即可。注意，这个东西的复杂度是 $O(n\log n)$ 的（只是常数非常大）。

多项式快速幂

显然有：

$$F^k(z) = \exp(\ln F(z) \times k)$$

有些细节，如果 $F(z)$ 常数项不为 $1$ ，若不为 $0$ ，直接给所有项乘上常数项的逆元，否则，系数平移一下即可。

时间复杂度 $O(n\log n)$

多项式多点求值

给定 $F(z)$ 求 $F(a_1),F(a_2),\dots,F(a_m)$

这里写两种做法

一种常数很大的做法

考虑这样一个东西 $F(a_i) = F(z) \bmod {z-a_i}$ 。

为啥呢？考虑带余除法

$$F(z) = A(z)(z - a_i) + B(z)$$

带入 $z = a_i$

$$F(a_i) = B(a_i)$$

而我们知道 $B(z) = F(z) \bmod z - a_i$ 。

考虑另一个事实：如果 $B(z) = A(z)C(z)$ 那么 $F \bmod B \bmod C = F \bmod C$ 。

这个想一想就发现挺显然的吧。。

现在考虑分治，首先给 $[1,n]$ 传入 $F(z) \bmod \prod_{i=1}^m (z-a_i)$ 。然后考虑对于区间 $[l,r]$ ，设它被传入的多项式是 $F_{[l,r]} (z)$ ，那么：

• 给 $[l,mid]$ 传 $F_{[l,r]}(z) \bmod \prod _{i=l}^{mid} (z-a_i)$
• 给 $[mid + 1,r]$ 传 $F_{[l,r]}(z) \bmod \prod _{i=mid + 1}^{r} (z-a_i)$ 。

最终叶子节点一定会剩下一个常数，即为所求。

复杂度是 $O(n\log n + m\log^2 n)$ 常数大到离谱，估计是跑不过 $10^5$ 的。

一种常数优秀点的做法

我们定义一下差卷集 ，这里 $f_i,g_i$ 表示 $F(z),G(z)$ 的 $i$ 次项系数。

$$mult(F(z),G(z)) = \sum_{i=0}^n z^i\sum_{j - k = i} f_jg_k$$

然后我们发现，$F(a_i) = [z^0] mult(F(z),\frac 1 {1-a_iz})$ 。因为 $\frac 1 {1-a_iz} = 1 + a_iz + a_i^2z^2 + \cdots$ ，这个东西和 $F(z)$ 做差卷积后显然得到的是 $\sum_{j\ge 0} f_ja_i^j$ 这正好就是 $F(a_i)$ 定义。

还有一个 $mult$ 的性质

$$mult(F(z),G(z)H(z)) = mult(mult(F(z),G(z)),H(z))$$

为啥呢？考虑前面那个式子 $z^t$ 的系数相当于 $\sum_{i - (j + k) = t} f_ig_jh_k$ 而后面的是 $\sum_{i-j-k = t} f_ig_jh_k$ ，它俩本质相同的。

于是我们还是类似刚才的分治，在 $[1,n]$ 传入一个 $mult(F(z) , \frac 1 {\prod_{i=1}^m (1-a_iz)})$ 。考虑当前在区间 $[l,r]$ 被传入的多项式是 $F_{[l,r]}(z)$ 那么

• 向左边传 $mult(F_{[l,r]}(z), {\prod_{i=mid+1}^r (1 - a_iz)})$
• 向右边传 $mult(F_{[l,r]}(z), {\prod_{i=l}^{mid} (1 - a_iz)})$

明显，到叶子就只剩下 $F(a_i) = [z^0] mult(F(z),\frac 1 {1-a_iz})$ 了。

常数很小，传说中的 1s5e5 多点求值。

---

经典操作

$n$ 个点有标号联通图计数

有容斥的做法，曾经写过博客，这里不说了。

考虑设 $n$ 个点无向图的 EGF 为 $F(z)$ ， $n$ 个点的无向图个数为 $G(z)$ 。

我们考虑枚举一下无向图中包含了多少个联通块，由于加入这些联通块的时候是涉及顺序了的，所以还得除以联通块的阶乘。

$$F(z) = \sum_{i\ge 0} \frac{G^i(z)}{i!} = \exp G(z)$$

也就是说

$$G(z) = \ln F(z)$$

uoj #50 链式反应

题目本质上是让你解 $F’(z) = \frac 1 2 A(z)F^2(z) + 1$

抽象一下，相当于是求一个形式幂级数 $G(z)$ ，求 $G’(z) = H(G(z))$

考虑牛顿迭代，设 $x_0’ = H(G(z)) \pmod{z^{n}}$ ，则要求一个 $x$ 满足 $x’ = H(G(z)) \pmod{z^{2n}}$ 。那么把后面那个式子在 $x_0$ 处展开

$$x' = H(x_0) + H'(x_0) (x - x_0) \pmod {z^{2n}}$$

然后可以用上一个用来求解这种方程的管用套路：

$$x' - H'(x_0)x = H(x_0) - H(x_0)x_0$$

我们给两边分别乘上 $r = e^{-\int H’(x_0) \text{d}z} $

$$x'r - H'(x_0)xr = (H(x_0) - H(x_0)x_0)r$$

看着没用，实际上发现左边那一坨就是 $(xr)’$ 。。用链式法则展开发现非常对。。

也就是说

$$(xr)' = (H(x_0) - H(x_0)x_0) r$$

我们知道 $r$ 是可以求的，$H(x_0),x_0$ 已知，于是就可以算出 $x$ 了。