多项式进阶

洛必达法则

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

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

则

$$\lim_{x\to x_0}\frac{f(x)}{g(x)}=\lim_{x\to x_0}\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)$，且$\deg R<\deg B$。注意这里不是模意义下。$\deg A$表示多项式最高次项的次数。

定义一个变换

$$F^R(x)=x^{\deg F}F\left(\frac{1}{x}\right)$$

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

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

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

$$\begin{aligned} x^{\deg A}A\left(\frac{1}{x}\right)&=x^{\deg B}B\left(\frac{1}{x}\right)x^{\deg Q}Q\left(\frac{1}{x}\right)+x^{\deg A}R\left(\frac{1}{x}\right)\\ A^R(x)&=B^R(x)Q^R(x)+R^R(x)x^{\deg A-\deg B+1} \end{aligned}$$

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

$$A^R(x)=B^R(x)Q^R(x)\pmod{x^{\deg A-\deg B+1}}$$

这样我们可以求出$Q^R\bmod{x^{\deg A-\deg B+1}}$。

由于$\deg Q<\deg A-\deg B+1$，因此$Q^R\bmod x^{\deg A-\deg B+1}=Q^R$。于是

$$Q^R(x)=\frac{A^R(x)}{B^R(x)}\pmod{x^{\deg A-\deg B+1}}$$

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

时间复杂度$O(n\log_2n)$。

多点求值

给出$F(x)$，求$F(a_1),F(a_2),\cdots,F(a_m)$，其中$m$与$\deg F$同阶。

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

容易发现$L(a_1)=L(a_2)=\cdots =L(a_{\lfloor\frac{m}{2}\rfloor})=0$。那么构造$F_L(x)=F(x)\bmod L(x)$。显然有$F_L(a_i)=F(a_i),i\in[1,\lfloor\frac{m}{2}\rfloor]$满足。因此左边递归下去求值。右边同理。

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

快速插值

给出$(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$。那么我们可以唯一确定一个$n-1$次多项式。求出这个多项式。

用拉格朗日插值可以得到

$$\begin{aligned} F(x)&=\sum_{i=1}^n\prod_{j\ne i}\frac{(x-x_j)}{(x_i-x_j)}y_i\\ &=\sum_{i=1}^n\frac{\prod_{j\ne i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)}y_i \end{aligned}$$

分上下两部分处理。

第一部分

考虑对于每个$i$求出$V_i=\prod_{j\ne i}(x_i-x_j)$。

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

容易发现$V_i=\dfrac{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,\cdots,x_n$处的点值即可。这样就求出了所有$V_i$。时间复杂度$O(n\log_2^2n)$。

第二部分

求出$V_i$后，原式可以表示为

$$F(x)=\sum_{i=1}^n\frac{y_i}{V_i}\prod_{j\ne i}(x-x_j)$$

同样考虑分治，设

$$\begin{aligned} M_L&=\prod_{i=1}^{n/2}(x-x_i)\\ M_R&=\prod_{i=n/2+1}^n(x-x_i)\\ F_L&=\sum_{i=1}^{n/2}\frac{y_i}{V_i}\prod_{j=1,j\ne i}^{n/2}(x-x_j)\\ F_R&=\sum_{i=n/2+1}^{n}\frac{y_i}{V_i}\prod_{j=n/2+1,j\ne i}^{n}(x-x_j) \end{aligned}$$

那么如果我们求出了这 4 个多项式，那么可以得到$F=F_LM_R+F_RM_L$。两边递归求解即可。

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

多项式复合逆

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

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

拉格朗日反演

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

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

还有一个扩展形式：

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

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

大朋友与多叉树

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

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

定义两个普通生成函数

$$F(x)=\sum_{n\in D}x^n\\ G(x)=\sum_{n\ge 1}g_nx^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}]\left(\frac{x}{x-F(x)}\right)^s$$

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

时间复杂度$O(n\log_2n)$。

仙人掌计数

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

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

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

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

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

$$F(x)=x\exp \left(F(x)+\sum_{i\ge 2}\frac{F^i(x)}{2}\right)$$

稍作整理得到

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

考虑牛顿迭代法。

方法一

设

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

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

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

对$G$求导得到

$$\begin{aligned} G'(F(x))&=\left(x\exp \left(\frac{2F(x)-F^2(x)}{2-2F(x)}\right)\right)'-1\\ &=x\left(\exp \left(\frac{2F(x)-F^2(x)}{2-2F(x)}\right)\right)'-1\\ &=x\exp \left(\frac{2F(x)-F^2(x)}{2-2F(x)}\right)\left(\frac{2F(x)-F^2(x)}{2-2F(x)}\right)'-1\\ &=x\exp \left(\frac{2F(x)-F^2(x)}{2-2F(x)}\right) \left(1+\frac{2(2F(x)-F^2(x))}{(2-2F(x))^2}\right)-1 \end{aligned}$$

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

最后得到

$$F(x)=F_0(x)- \frac{x\exp \left(\frac{2F_0(x)-F_0^2(x)}{2-2F_0(x)}\right)-F_0(x)}{x\exp \left(\frac{2F_0(x)-F_0^2(x)}{2-2F_0(x)}\right) \left(1+\frac{2(2F_0(x)-F_0^2(x))}{(2-2F_0(x))^2}\right)-1} \pmod {x^n}$$

方法二

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

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

因此设

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

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

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

因此可以得到

$$\begin{aligned} F(x)&=F_0(x)- \frac{F_0(x)\exp \left(\frac{2F_0(x)-F_0^2(x)}{2F_0(x)-2}\right)-x} {\exp\left( \frac{2F_0(x)-F_0(x)^2}{2F_0(x)-2} \right) \left(1-F_0(x)\left(1+\frac{2(2F_0(x)-F_0(x)^2)}{(2F_0(x)-2)^2}\right)\right)}\\ &=F_0(x)- \frac{F_0(x)-x\exp \left(\frac{2F_0(x)-F_0^2(x)}{2-2F_0(x)}\right)} {1-F_0(x)\left(1+\frac{2(2F_0(x)-F_0(x)^2)}{(2-2F_0(x))^2}\right)} \end{aligned}\pmod{x^n}$$

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

代码

点双连通图计数

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

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

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

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

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

$$G(x)=x\exp \left(\sum_{i\ge 1}\frac{f_{i+1}G^i(x)}{i!}\right)=x\exp F'(G(x))$$

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

$$\begin{aligned} G(G^I(x))&=G^I(x)\exp F'(G(G^I(x)))\\ x&=G^I(x)\exp F'(x)\\ F'(x)&=\ln \frac{x}{G^I(x)} \end{aligned}$$

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