多项式进阶

洛必达法则

若函数 $f$ 和 $g$ 满足以下条件：

$x \to x_{0} lim f (x) = x \to x_{0} lim g (x) = 0$ ；
在 $x$ 的某空邻域 $U^{\circ} (x_{0})$ 内两者均可导，且 $g^{'} (x) \neq = 0$ ；
$x \to x_{0} lim \frac{f ^{'} ( x )}{g ^{'} ( x )} = A$ ，其中 $A$ 可为非正常极限。

则

x \to x_{0} lim \frac{f ( x )}{g ( x )} = x \to x_{0} lim \frac{f ^{'} ( x )}{g ^{'} ( x )} = A

通俗地说，如果 $f (x), g (x)$ 在 $x_{0}$ 处的极限都是 $0$ ，那么 $\frac{f ( x )}{g ( x )}$ 在 $x_{0}$ 处的极限可以通过他们的导数来求。

多项式除法

给出多项式 $A (x), B (x)$ ，求出 $D (x), R (x)$ ，满足 $A (x) = B (x) Q (x) + R (x)$ ，且 $de g R < de g B$ 。注意这里不是模意义下。 $de g A$ 表示多项式最高次项的次数。

定义一个变换

F^{R} (x) = x^{d e g F} F (\frac{1}{x})

该变换的实质是把多项式的系数翻转过来了。代入 $\frac{1}{x}$ 得到

A (\frac{1}{x}) = B (\frac{1}{x}) Q (\frac{1}{x}) + R (\frac{1}{x})

由于 $de g Q = de g A - de g B$ ，那么不妨设 $de g R = de g B - 1$ 。稍作变换得到

x^{d e g A} A (\frac{1}{x}) A^{R} (x) = x^{d e g B} B (\frac{1}{x}) x^{d e g Q} Q (\frac{1}{x}) + x^{d e g A} R (\frac{1}{x}) = B^{R} (x) Q^{R} (x) + R^{R} (x) x^{d e g A - d e g B + 1}

那么容易发现，在模 $x^{d e g A - d e g B + 1}$ 意义下， $R^{R}$ 就没了：

A^{R} (x) = B^{R} (x) Q^{R} (x) (mod x^{d e g A - d e g B + 1})

这样我们可以求出 $Q^{R} mod x^{d e g A - d e g B + 1}$ 。

由于 $de g Q < de g A - de g B + 1$ ，因此 $Q^{R} mod x^{d e g A - d e g B + 1} = Q^{R}$ 。于是

Q^{R} (x) = \frac{A ^{R} ( x )}{B ^{R} ( x )} (mod x^{d e g A - d e g B + 1})

这样使用多项式求逆即可得到 $Q^{R}$ ，反代回去可求出 $R$ 。

时间复杂度 $O (n lo g_{2} n)$ 。

多点求值

给出 $F (x)$ ，求 $F (a_{1}), F (a_{2}), \dots, F (a_{m})$ ，其中 $m$ 与 $de g F$ 同阶。

考虑分治。设 $L (x) = \prod_{i = 1}^{⌊ \frac{m}{2} ⌋} (x - a_{i})$ ， $R (x) = \prod_{i = ⌊ \frac{m}{2} ⌋ + 1}^{n} (x - a_{i})$ 。

容易发现 $L (a_{1}) = L (a_{2}) = \dots = L (a_{⌊ \frac{m}{2} ⌋}) = 0$ 。那么构造 $F_{L} (x) = F (x) mod L (x)$ 。显然有 $F_{L} (a_{i}) = F (a_{i}), i \in [1, ⌊ \frac{m}{2} ⌋]$ 满足。因此左边递归下去求值。右边同理。

时间复杂度 $O (m lo g_{2}^{2} m)$ 。在实现的过程中需要预先把所有的 $\prod (x - a_{i})$ 函数都存下来，因此空间复杂度是 $O (m lo g_{2} m)$ 。

快速插值

给出 $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})$ 。那么我们可以唯一确定一个 $n - 1$ 次多项式。求出这个多项式。

用拉格朗日插值可以得到

F (x) = i = 1 \sum n j \neq = i \prod \frac{( x - x _{j} )}{( x _{i} - x _{j} )} y_{i} = i = 1 \sum n \frac{\prod _{j \neq = i} ( x - x _{j} )}{\prod _{j \neq = i} ( x _{i} - x _{j} )} y_{i}

分上下两部分处理。

第一部分

考虑对于每个 $i$ 求出 $V_{i} = \prod_{j \neq = i} (x_{i} - x_{j})$ 。

设 $M (x) = \prod_{i = 1}^{n} (x - x_{i})$ 。那么 $M (x)$ 可以分治 NTT 计算出来，时间复杂度 $O (n lo g_{2} n)$ 。

容易发现 $V_{i} = \frac{M ( x )}{x - x _{i}}$ 。但是如果我们直接做 $n$ 次多项式求逆的话复杂度就不对了。

利用洛必达法则，设 $Q (x) = x - x_{i}$ 。因为 $M (x_{i}) = Q (x_{i}) = 0$ ，且两个函数都在邻域内可导，因此得到

V_{i} = \frac{M ( x )}{Q ( x )} (x_{i}) = \frac{M ^{'} ( x )}{Q ^{'} ( x )} (x_{i}) = M^{'} (x_{i})

那么对 $M^{'} (x)$ 求出在 $x_{1}, x_{2}, \dots, x_{n}$ 处的点值即可。这样就求出了所有 $V_{i}$ 。时间复杂度 $O (n lo g_{2}^{2} n)$ 。

第二部分

求出 $V_{i}$ 后，原式可以表示为

F (x) = i = 1 \sum n \frac{y _{i}}{V _{i}} j \neq = i \prod (x - x_{j})

同样考虑分治，设

M_{L} M_{R} F_{L} F_{R} = i = 1 \prod n /2 (x - x_{i}) = i = n /2 + 1 \prod n (x - x_{i}) = i = 1 \sum n /2 \frac{y _{i}}{V _{i}} j = 1, j \neq = i \prod n /2 (x - x_{j}) = i = n /2 + 1 \sum n \frac{y _{i}}{V _{i}} j = n /2 + 1, j \neq = i \prod n (x - x_{j})

那么如果我们求出了这 4 个多项式，那么可以得到 $F = F_{L} M_{R} + F_{R} M_{L}$ 。两边递归求解即可。

时间复杂度 $O (n lo g_{2}^{2} n)$ ，空间复杂度 $O (n lo g_{2} n)$ ，因为多点求值带一个 $O (n lo g_{2} n)$ 的空间复杂度。而第二部分的计算是可以把空间减小到 $O (n)$ 的，不过直接动态开空间也只增大了空间常数，没有改变空间复杂度。

多项式复合逆

对于两个多项式函数 $F (x), G (x)$ ，如果 $F (G (x)) = x$ ，称 $F, G$ 互为复合逆。

容易证明 $G (F (x)) = F (G (x)) = x$ 。但是多项式复合逆没有时间复杂度 $O (n lo g_{2} n)$ 的做法。但可以使用拉格朗日反演在 $O (n lo g_{2} n)$ 的时间内计算出某一项。

拉格朗日反演

对于两个多项式函数 $F (x), G (x)$ ，如果 $F (G (x)) = x$ ，那么

[x^{n}] G (x) = \frac{1}{n} [x^{n - 1}] (\frac{x}{F ( x )})^{n}

还有一个扩展形式：

[x^{n}] H (G (x)) = \frac{1}{n} [x^{n - 1}] H^{'} (x) (\frac{x}{F ( x )})^{n}

其中 $H (x)$ 是另一个多项式函数。

大朋友与多叉树

题意：求有多少棵有根树，满足有 $s$ 个叶子结点，内部结点的儿子数都属于集合 $D$ ，且 $1 \in / D$ 。注意，儿子之间是有顺序的。

例如当 $s = 4, D = {2, 3}$ 时：

polynomial-pro1

定义两个普通生成函数

F (x) = n \in D \sum x^{n} G (x) = n \geq 1 \sum g_{n} x^{n}

其中 $g_{n}$ 是 $s = n$ 的答案。考虑根结点的孩子数为 $a$ ，此时方案数的生成函数显然为 $G^{a} (x)$ 。从这个思路出发，可以得到

F (G (x)) + x = G (x)

加上一个 $x$ 是考虑 $s = 1$ 的情况。可以得到 $G (x) - F (G (x)) = x$ ，因此 $x - F (x)$ 与 $G (x)$ 互为复合逆。

使用拉格朗日反演得到

[x^{s}] G (x) = \frac{1}{s} [x^{s - 1}] (\frac{x}{x - F ( x )})^{s}

在模 $x^{s + 1}$ 意义下直接求值即可。一个技巧是把后面的式子转化为 $(1 - \frac{F ( x )}{x})^{- s}$ 的形式，这样常数项为 1，可以多项式 $ln$ 来求幂。

时间复杂度 $O (n lo g_{2} n)$ 。

仙人掌计数

仙人掌：如果一个简单无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

求 $n$ 个点带标号的仙人掌数量。

考虑有根仙人掌的指数生成函数为 $F (x)$ 。那么求出来后把方案数除以 $n$ 就是答案。我们可以将仙人掌的构成分成两种部分：

从根结点连出去的独立边，相当于接一个仙人掌出去。一条边连出去的生成函数是 $F (x)$ ，多条边之间不区分顺序，因此方案数是 $exp F (x)$ 。
包含根结点的一个简单环，环上除了根结点之外的每个结点都挂一个仙人掌。由于我们要考虑环上结点之间的顺序，因此假设环长为 $i + 1$ ，那么 $i$ 个仙人掌按序排列的生成函数是 $F^{i} (x)$ 。考虑到是一个环，因此每个排列被正着反着各算了一次，因此长度为 $i + 1$ 的环的生成函数是 $\frac{F ^{i} ( x )}{2}$ 。那么一个环的生成函数就是 $i \geq 2 \sum \frac{F ^{i} ( x )}{2}$ 。多个环之间是不区分顺序的，因此多个环的方案数是 $exp (i \geq 2 \sum \frac{F ^{i} ( x )}{2})$ 。

综上，环和独立边互不相关，总方案数是 $exp (F (x) + i \geq 2 \sum \frac{F ^{i} ( x )}{2})$ ，再加上根结点本身得到

F (x) = x exp (F (x) + i \geq 2 \sum \frac{F ^{i} ( x )}{2})

稍作整理得到

F (x) = x exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )})

考虑牛顿迭代法。

方法一

设

G (F (x)) = x exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )}) - F (x)

那么显然我们要求 $G (F (x)) = 0 (mod x^{n + 1})$ 。应用牛顿迭代得到

F (x) = F_{0} (x) - \frac{G ( F _{0} ( x ))}{G ^{'} ( F _{0} ( x ))} (mod x^{n})

对 $G$ 求导得到

G^{'} (F (x)) = (x exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )}))^{'} - 1 = x (exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )}))^{'} - 1 = x exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )}) (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )})^{'} - 1 = x exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )}) (1 + \frac{2 ( 2 F ( x ) - F ^{2} ( x ))}{( 2 - 2 F ( x ) ) ^{2}}) - 1

如何理解式子中的 $x$ ？我们把它理解为与 $F (x)$ 不相关的一个常量即可。常量的导数是 $0$ 。

最后得到

F (x) = F_{0} (x) - \frac{x exp ( \frac{2 F _{0} ( x ) - F _{0}^{2} ( x )}{2 - 2 F _{0} ( x )} ) - F _{0} ( x )}{x exp ( \frac{2 F _{0} ( x ) - F _{0}^{2} ( x )}{2 - 2 F _{0} ( x )} ) ( 1 + \frac{2 ( 2 F _{0} ( x ) - F _{0}^{2} ( x ))}{( 2 - 2 F _{0} ( x ) ) ^{2}} ) - 1} (mod x^{n})

方法二

方才 $F (x)$ 的式子可以变换为

F (x) = x exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 - 2 F ( x )}) F (x) exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 F ( x ) - 2}) - x = 0

因此设

G (F (x)) = F (x) exp (\frac{2 F ( x ) - F ^{2} ( x )}{2 F ( x ) - 2}) - x

同样的方法，对 $G$ 求导得到

G^{'} (F (x)) = exp (\frac{2 F ( x ) - F ( x ) ^{2}}{2 F ( x ) - 2}) (1 - F (x) (1 + \frac{2 ( 2 F ( x ) - F ( x ) ^{2} )}{( 2 F ( x ) - 2 ) ^{2}}))

因此可以得到

F (x) = F_{0} (x) - \frac{F _{0} ( x ) exp ( \frac{2 F _{0} ( x ) - F _{0}^{2} ( x )}{2 F _{0} ( x ) - 2} ) - x}{exp ( \frac{2 F _{0} ( x ) - F _{0} ( x ) ^{2}}{2 F _{0} ( x ) - 2} ) ( 1 - F _{0} ( x ) ( 1 + \frac{2 ( 2 F _{0} ( x ) - F _{0} ( x ) ^{2} )}{( 2 F _{0} ( x ) - 2 ) ^{2}} ) )} = F_{0} (x) - \frac{F _{0} ( x ) - x exp ( \frac{2 F _{0} ( x ) - F _{0}^{2} ( x )}{2 - 2 F _{0} ( x )} )}{1 - F _{0} ( x ) ( 1 + \frac{2 ( 2 F _{0} ( x ) - F _{0} ( x ) ^{2} )}{( 2 - 2 F _{0} ( x ) ) ^{2}} )} (mod x^{n})

两种迭代方式是等价的。由于是 EGF 最后别忘了乘上 $n!$ 。

代码

点双连通图计数

如果一个无向连通图删去任意一个点都仍然是连通的，我们就称为点双连通图。

求 $n$ 个点带标号点双连通图的个数。

同样地，设 $F (x) = \sum_{n \geq 1} f_{n} \frac{x ^{n}}{n !}$ 表示 $n$ 个点的点双连通图的 EGF。设 $G (x)$ 表示 $n$ 个点有根连通图的 EGF。

设 $H (x) = \sum_{n \geq 0} 2^{(2 n)} \frac{x ^{n}}{n !}$ 表示带标号无向图数的生成函数，那么得到 $G (x) = x (ln H (x))^{'}$ 。

我们考虑用 $F$ 表示 $G$ 。考虑有根无向图的包含根结点的点双连通分量。假设大小为 $i + 1$ ，那么除了根结点之外的点都可以挂一个有根连通图，因此方案数是 $\sum_{i \geq 1} \frac{G ^{i} ( x )}{i !}$ 。对于 $i$ 个不区分顺序的有根连通图的根结点，再加上根结点，因此一个点双连通分量的方案数是 $\sum_{i \geq 1} \frac{f _{i + 1} G ^{i} ( x )}{i !}$ 。多个点双连通分量之间不区分顺序，因此总方案数是 $exp (\sum_{i \geq 1} \frac{f _{i + 1} G ^{i} ( x )}{i !})$ 。再加上根结点本身得到

G (x) = x exp (i \geq 1 \sum \frac{f _{i + 1} G ^{i} ( x )}{i !}) = x exp F^{'} (G (x))

然而这个方程无法牛顿迭代。设 $G$ 的复合逆是 $G^{I}$ ，那么得到

G (G^{I} (x)) x F^{'} (x) = G^{I} (x) exp F^{'} (G (G^{I} (x))) = G^{I} (x) exp F^{'} (x) = ln \frac{x}{G ^{I} ( x )}

据说使用扩展拉格朗日反演可以解决。

文章目录