多项式插值

定义：给定 $n+1$ 个点值 ${(x_i,y_i)}{i=0}^{n}$，所有 $x_i$ 互不相等，求解 $n$ 次多项式 $F(x)=\sum{i=0}^{n}f_i\cdot x^i$ 满足 $\forall i=0,1,\dots,n$，有 $F(x_i)=y_i$。称为多项式插值或代数插值。

Taylor 插值法

考虑 Taylor 多项式：

\[P_n(x)=\sum_{k=0}^{n}\frac{f^{(k)}(x_0)}{k!}\cdot(x-x_0)^k\]

若已知 $0\sim n$ 次导，即 $P_n^{(k)}(x_0)=f^{(k)}(x_0)$，则逆用 Taylor 多项式得：

\[f(x)=\sum_{k=0}^{n}\frac{f^{(k)}(x_0)}{k!}\cdot(x-x_0)^k+R_{n+1}(x)\]

其中 $R_{n+1}(x)$ 为 Lagrange 余项，其表达式为:

\[R_{n+1}(x)=\frac{f^{(n+1)}(\xi)}{(n+1)}\cdot(x-x_0)^{n+1}\]

$\xi$ 的数值介于 $x_0$ 到 $x$ 之间。

时间复杂度：$O(n^2)$。

Lagrange 插值法

尝试对于每个点 $i$ 构造函数 $f_i(x)$（称为插值基函数）使得 $f_i(x_i)=y_i$ 且 $\forall j\not=i$, 有 $f_i(x_j)=0$。

容易得出插值基函数的构造：

\[f_i(x)=y_i\cdot\prod_{j\not=i}\frac{x-x_j}{x_i-x_j}\]

将所有插值基函数叠加得到的多项式 $f(x)$ 即可满足要求：

\[f(x)=\sum_{i=0}^{n}y_i\cdot\prod_{j\not=i}\frac{x-x_j}{x_i-x_j}\]

时间复杂度：$O(n^2)$。

重心 Lagrange 插值（I）

朴素 Lagrange 插值对动态插入新的点值的支持性差，考虑在 Lagrange 插值的基础上构造支持 $O(n)$ 插点的方法。

令 $l(x)=\prod_{i=0}^{n}(x-x_i)$，则代入 $f(x)$ 有：

\[\begin{align*} f(x)&=\sum_{i=0}^{n}y_i\cdot\frac{l(x)}{(x-x_i)\cdot\prod_{j\not=i}(x_i-x_j)}\\ &=l(x)\cdot\sum_{i=0}^{n}\frac{y_i}{(x-x_i)\cdot\prod_{j\not=i}(x_i-x_j)} \end{align*}\]

设重心权为：

\[w_i=\frac{y_i}{\prod_{j\not=i}(x_i-x_j)}\]

此时：

\[f(x)=l(x)\cdot\sum_{i=0}^{n}\frac{w_i}{x-x_i}\]

此时新加入点只需 $O(n)$ 地更新重心权 $w_i$ 即可。

该构造具有向后稳定性。

重心 Lagrange 插值（II）

使用重心 Lagrange 插值（I）的方法插值 $g(x)\equiv 1$，得：

\[g(x)=l(x)\cdot\sum_{i=0}^{n}\frac{w_i}{x-x_i}\]

因此：

\[f(x)=\frac{f(x)}{g(x)}=\cdot\frac{\sum_{i=0}^{n}y_i\cdot\frac{w_i}{x-x_i}}{\sum_{i=0}^{n}\frac{w_i}{x-x_i}}\]

该计算方法具有向前稳定性。

Newton 插值法

Newton 插值用于稳定精确地计算动态加入点值的插值多项式。

差商

一阶差商：

\[f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}\]

二阶差商：

\[f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}\]

以此类推，$n$ 阶差商有：

\[f[x_L,\dots,x_{L+n}]=\frac{f[x_{L+1},x_{L+n}]-f[x_{L},x_{L+n-1}]}{x_{L+n}-x_L}\]

Newton 插值公式

Newton 插值公式具有两种形式。

牛顿前插公式（forward interpolation formula）：

\[P(x)=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\dots\]

牛顿后插公式（backward interpolation formula）：

\[P(x)=f(x_n)+f[x_{n-1},x_n](x-x_n)+f[x_{n-2},x_{n-1},x_n](x-x_n)(x-x_{n-1})+\dots\]

时间复杂度：$O(n^2)$。

生成函数

普通生成函数（OGF）

定义：序列 $g$ 的普通生成函数定义为如下形式幂级数：

\[G(z)=\sum_ng_nz^n\]

基本运算

设 $\mathbb{G}$ 表示普通生成函数的集合。

加法：普通生成函数相加时系数数组相加，$(\mathbb{G},+)$ 构成 Abel 群。

\[\alpha F(z)+\beta G(z)=\sum_n(\alpha f_n+\beta g_n)z^n\]

乘法：普通生成函数相乘时系数数组做卷积，$(\mathbb{G},\cdot)$ 构成半群。

\[F(z)\cdot G(z)=\sum_n(\sum_kf_kg_{n-k})z^n\]

综上，$(\mathbb{G},+,\cdot)$ 构成环。

【更多运算】（摘自《具体数学》）
$\alpha F(z)+\beta G(z)=\sum_n(\alpha f_n+\beta g_n)z^n$（加法）
$z^m\cdot G(z)=\sum_{n}g_{n-m}z^n,m\geq 0$（向右平移）
$\frac{G(z)-g_0-g_1\cdot z-\dots-g_{m-1}\cdot z^{m-1}}{z^m}=\sum_{n\geq 0}g_{n+m}z^n,m\geq 0$（向左平移）
$G(cz)=\sum_nc^ng_nz^n$
$G’(z)=\sum_n(n+1)g_{n+1}z^n$（一阶导数）
$z\cdot G’(z)=\sum_nng_nz^n$（一阶导数的平移）
$\int_{0}^{z}G(t)\text{d}t=\sum_{n\geq 1}\frac{1}{n}g_{n-1}z^n$（积分）
$F(z)\cdot G(z)=\sum_n(\sum_kf_kg_{n-k})z^n$（乘法）
$\frac{1}{1-z}\cdot G(z)=\sum_n(\sum_{k\leq n}g_k)z^n$（乘法在 $F(z)=\sum_n z^n$ 时的特化）

注意《具体数学》的语境下，生成函数系数数组的下标可取所有整数。

封闭形式

从《具体数学》截的糊得没边的图，一些复杂生成函数的封闭形式求解可以考虑通过基础数列进行运算组合得到。

解递归式

给定某个递归形式的数列 $\langle g_n\rangle$，求 $g_n$ 的封闭形式，可以分作四步进行：

1. 用数列中的其他元素写出表示 $g_n$ 的单个方程，该方程应对任意整数 $n$ 成立。（令 $g_{-1}=g_{-2}=\dots=0$。）
2. 使用 $z^n$ 乘方程的两边，并对所有 $n$ 求和，左边就给出和式 $\sum_ng_nz^n$，即生成函数 $G(z)$，右边处理为包含 $G(z)$ 的另外一个形式。
3. 解所得方程，得到 $G(z)$ 的封闭形式。
4. 展开 $G(z)$ 的封闭形式，取出 $z^n$ 的系数 $[z^n]G(z)$，即为 $g_n$ 的封闭形式。

例：Fibonacci 数列

【Step 1】 显然有方程 $g_n=g_{n-1}+g_{n-2}+[n=1]$。

【Step 2】 按以下方式转换式子：

\[\begin{align*} G(z)&=\sum_ng_nz^n=\sum_ng_{n-1}z^n+\sum_ng_{n-2}z^n+\sum_n[n=1]z^n\\ &=\sum_ng_nz^{n+1}+\sum_ng_nz^{n+2}+z\\ &=zG(z)+z^2G(z)+z \end{align*}\]

【Step 3】 对以上式子移项解方程得：

\[G(z)=\frac{z}{1-z-z^2}\]

【Step 4】 考虑生成函数展开为幂级数的一般化方法。

给定任意有理函数 $R(z)=\frac{P(z)}{Q(z)}$，其中 $P(z),Q(z)$ 为多项式。

我们考虑一类系数具有很好的形式的有理函数：

\[\frac{a}{(1-\rho z)^{m+1}}=\sum_{n\geq 0}\binom{n+m}{m}a\rho^nz^n\]

随后考虑使用这类函数构造一个有限和式：

\[S(z)=\frac{a_1}{(1-\rho_1z)^{m_1+1}}+\frac{a_2}{(1-\rho_2z)^{m_2+1}}+\dots+\frac{a_l}{(1-\rho_lz)^{m_l+1}}\]

同样具有很好的系数：

\[[z^n]S(z)=a_1\binom{n+m_1}{m_1}\rho_1^n+a_2\binom{n+m_2}{m_2}\rho_2^n+\dots+a_l\binom{n+m_l}{m_l}\rho_l^n\]

接下来证明所有满足 $R(0)\not=\infty$ 的有理函数 $R(z)$ 均可表示为

\[R(z)=S(z)+T(z)\]

其中 $S(z)$ 为前文所示的构造，$T(z)$ 为一个多项式。注意到，当 $z=\frac{1}{\rho_1},\frac{1}{\rho_2},\dots,\frac{1}{\rho_l}$ 时，$S(z)=0$，如果希望将 $R(z)$ 表示为 $S(z)+T(z)$ 的形式，取 $\alpha_k$ 满足 $Q(\alpha_k)=0$，则 $\alpha$ 与 $\rho$ 一一对应，且 $\alpha_k\cdot\rho_k=1$。

设 $Q(z)$ 形如：

\[Q(z)=q_0+q_1z+\cdot+q_mz^m\]

其中 $q_0,q_m$ 均不等于 $0$。

其反射多项式为：

\[Q^R(z)=q_0z^m+q_1z^{m-1}+\cdot+q_m\]

此时存在关系：

\[Q^R(z)=q_0(z-\rho_1)\dots(z-\rho_m)\Leftrightarrow Q(z)=q_0(1-\rho_1z)\dots(1-\rho_mz)\]

因此 $Q^R(z)$ 的零点与 $Q(z)$ 的零点一一对应且对应的两个根互为倒数，如果对 $Q^R(z)$ 进行因子分解，即可得到要求到的数 $\phi_k$。

在 Fibonacci 数列中，有：

\[Q(z)=1-z-z^2,Q^R(z)=z^2-z-1\]

使用二次求根公式得到两根：

\[\phi=\frac{1+\sqrt{5}}{2},\hat\phi=\frac{1-\sqrt{5}}{2}\]

从而得到 $Q^R(z)=(z-\phi)(z-\hat\phi)$ 以及 $Q(z)=(1-\phi z)(1-\hat\phi z)$。

结果可以放在下一个部分的一般性推导后给出。

定理：不同根的有理展开

如果 $R(z)=\frac{P(z)}{Q(z)}$，其中 $Q(z)=q_0(1-\rho_1z)\dots(1-\rho_lz)$，而所有 $\rho_k$ 互不相同，若 $P(z)$ 是一个次数小于 $l$ 的多项式，那么：

\[\begin{align*} [z^n]R(z)=a_1\rho_1^n+\dots+a_l\rho_l^m, && a_k=\frac{-\rho_kP(\frac{1}{\rho_k})}{Q'(\frac{1}{\rho_k})} \end{align*}\]

【Proof】 设 $a_1,\dots,a_l$ 为所说的常数，若满足：

\[R(z)=\frac{P(z)}{Q(z)}=S(z)=\frac{a_1}{1-\rho_1z}+\dots+\frac{a_l}{1-\rho_lz}\]

那么定理成立，而通过证明 $z\rightarrow \frac{1}{\rho_k}$ 是函数 $T(z)=R(z)-S(z)\not=\infty$，即可证明 $R(z)=S(z)$。还可以证明，当 $z\rightarrow\infty$ 时 $T(z)\rightarrow 0$，从而说明 $T(z)$ 必等于 $0$。

设 $\alpha_k=\frac{1}{\rho_k}$，为证明 $\lim_{z\rightarrow\alpha_k}T(z)\not=\infty$，只需证明 $\lim_{z\rightarrow\alpha_k}T(z)=0$，因为 $T(z)$ 是 $z$ 的有理函数，从而希望证明：

\[\lim_{z\rightarrow\alpha_k}(z-\alpha_k)R(z)=\lim_{z\rightarrow\alpha_k}(z-\alpha_k)S(z)\]

由于 $(1-\rho_kz)=-\rho_k(z-\alpha_k)$，且 $\forall j\not=k$，有 $\dfrac{z-\alpha_k}{1-\rho_jz}\rightarrow 0$，右侧的极限为：

\[\lim_{z\rightarrow\alpha_k}a_k\frac{z-\alpha_k}{1-\rho_kz}=-\frac{\alpha_k}{\rho_k}\]

对于左侧，使用洛必达法则：

\[\lim_{z\rightarrow\alpha_k}(z-\alpha_k)\frac{P(z)}{Q(z)}=P(\alpha_k)\lim_{z\rightarrow\alpha_k}\frac{z-\alpha_k}{Q(z)}=\frac{P(\alpha_k)}{Q'(\alpha_k)}\]

从而证明定理成立。

【Fibonacci】 现在回到 Fibonacci 数列通项的推导，此时有 $P(z)=z$ 以及 $Q(z)=1-z-z^2=(1-\phi z)(1-\hat\phi z)$，故而 $Q’(z)=-1-2z$，则：

\[\frac{-\rho P(\frac{1}{\rho})}{Q'(\frac{1}{\rho})}=\frac{-1}{-1-\frac{2}{\rho}}=\frac{\rho}{\rho+2}\]

此时 $[z^n]R(z)$ 中 $\phi^n$ 的系数即为 $\frac{\phi}{\phi+2}=\frac{\sqrt{5}}{5}$，$\hat\phi^n$ 的系数为 $\frac{\hat\phi}{\hat\phi+2}=-\frac{\sqrt{5}}{5}$，因此得出结论：

\[[z^n]R(z)=\frac{\phi^n-\hat\phi^n}{\sqrt{5}}\]

* 定理：有理生成函数的一般展开

如果 $R(z)=\frac{P(z)}{Q(z)}$，其中 $Q(z)=q_0(1-\rho_1z)^{d_1}\dots(1-\rho_lz)^{d_l}$，而所有 $\rho_k$ 互不相同，$P(z)$ 是一个次数小于 $d_1+\dots+d_l$ 的多项式，那么：

\[\begin{align*} [z^n]R(z)=f_1(n)\rho_1^n+\dots+f_l\rho_l^n, && \forall n\geq 0 \end{align*}\]

其中每一个 $f_k(n)$ 都是一个次数为 $d_k-1$ 的多项式，且首项系数如下：

\[\begin{align*} a_k&=\frac{(-\rho_k)^{d_k}P(\frac{1}{\rho_k})d_k}{Q^{(d_k)}(\frac{1}{\rho_k})}\\ &=\frac{P(\frac{1}{\rho_k})}{(d_k-1)!q_0\prod_{j\not=k}(1-\frac{\rho_j}{\rho_k})^{d_j}} \end{align*}\]

【Proof】 我不会。

大致思路是考虑如下有理函数：

\[R(z)-\frac{a_1(d_1-1)!}{(1-\rho_1z)^{d_1}}-\dots-\frac{a_l(d_l-1)!}{(1-\rho_lz)^{d_l}}\]

该有理函数的分母多项式不能被任意 $(1-\rho_kz)^{d_k}$ 整除。

基于以上事实，对 $\max(d_1,\dots,d_l)$ 使用归纳法证明。

指数生成函数（EGF）

定义：序列 $g$ 的指数生成函数定义为如下形式幂级数：

\[\hat G(z)=\sum_{n\geq 0}g_n\frac{z^n}{n!}\]

指数函数 $e^x$ 恰对应数列 $\langle1,1,\dots,1 \rangle$ 的 EGF。

引入这一定义的必要性是毫无疑问的，前文《具体数学》表 7-2 中的几个 EGF，若使用 OGF 表达，将极为复杂，多半是发散的形式。

对于 OI 解决题目而言：

EGF 的形式自带消序功能，且乘法为二项卷积形式，自带归并定序功能。

因此若对有标号问题进行计数，使用 EGF；若对无标号问题进行计数，使用 OGF。

基本运算

求导：

\[\hat G(z)'=\sum_{n\geq 0}g_{n+1}\frac{z^n}{n!}\]

积分：

\[\int_{0}^{z}\hat G(z)\text{d}z=\sum_{n\geq 1}g_{n-1}\frac{z^n}{n!}\]

乘法：

\[\hat F(z)\hat G(z)=\sum_k\binom{n}{k}f_{n}g_{n-k}\]

生成函数与图论计数问题

以下内容一律采取更常见的有标号形式，也即使用 EGF 解决。

注意，并非所有有标号问题转化为无标号形式都只需简单地将 EGF 换为 OGF。

后面三个问题我不会，谁能教教 QWQ。

有标号无向连通图计数

设 $f_x$ 为 $x$ 个点的有标号无向连通图数量，$g_x$ 为 $x$ 个点的任意图数量。

根据组合意义，$g_x=2^{\binom{x}{2}}$。

数列 $\langle f_n\rangle,\langle g_n\rangle$ 分别构成指数生成函数 $\hat F(x),\hat G(x)$。

由组合意义，一般图可以视作若干连通图的并，则有关系：

\[\hat G(x)=\sum_{k\geq 1}\frac{\hat F^k(x)}{k!}=\exp\hat F(x)\]

因此：

\[\hat F(x)=\ln\hat G(x)\]

有标号置换环集合计数

说人话就是错排计数。

单个置换环即为圆排列，令 $F(x)$ 为元素数量大于等于 $2$ 的圆排列方案数 EGF，则：

\[\hat F(x)=\sum_{i\geq 2}\frac{x^i}{i}=-\ln(1-x)-x\]

与有标号无向连通图计数同样，所求 EGF 即为：

\[\hat G(x)=\exp\hat F(x)=\exp(-\ln(1-x)-x)\]

有标号有根树计数

直接考虑 Cayley 定理，所求 EGF 即为：

\[\hat G(x)=\sum_{k\geq 0}\frac{k^{k-1}}{k!}x^k\]

有标号基环树计数

基环树可以视作将一些有根树用一个环串起来形成的结构，由于有标号有根树的 EGF 为：

\[\hat F(x)=\sum_{k\geq 0}\frac{k^{k-1}}{k!}x^k\]

所求 EGF 即为：

\[\begin{align*} \hat G(x)&=\frac{1}{2}\sum_{k\geq 3}\frac{F^k(x)}{k!}\\ &=-\frac{1}{2}(\ln(1-F(x))-F(x)-F^2(x)) \end{align*}\]

有标号二分图计数

设答案生成函数为 $\hat G(x)$，有标号连通二分图的生成函数为 $\hat F(x)$。同样有：

\[\hat G(x)=\exp \hat F(x)\]

对 $\hat F(x)$ 计数，先考虑有标号二分染色图（不一定连通）的方案数量，枚举黑点数量有：

\[[x^n]\hat H(x)=\sum_{k=0}^{n}\binom{n}{k}2^{k(n-k)}\]

同样考虑通过有标号连通二分图组成有标号二分染色图，枚举连通块数量，而同一连通块有 $2$ 种染色方案，因此：

\[\hat H(x)=\sum_{k\geq 1}\frac{2^k\cdot\hat F^k(x)}{k!}=\exp 2\hat F(x)\]

推出：

\[\hat G(x)=\sqrt{\hat H(x)}\]

因此考虑计算 $\hat H(x)$，$\hat G(x)$ 即可通过多项式开根计算。

考虑 $\hat H(x)$ 的系数的计算，先考虑如下恒等式：

\[k(n-k)=\binom{n}{2}-\left(\binom{k}{2}+\binom{n-k}{2}\right)\]

代入原式有：

\[\begin{align*} [x^n]\hat H(x)&=\sum_{k=0}^{n}\frac{n!}{k!(n-k)!}\cdot\left(2^{\binom{n}{2}}\cdot 2^{-\binom{k}{2}}\cdot2^{-\binom{n-k}{2}}\right)\\ &=n!\cdot2^{\binom{n}{2}}\cdot\sum_{k=0}^{n}\left(\frac{2^{-\binom{k}{2}}}{k!}\cdot\frac{2^{-\binom{n-k}{2}}}{(n-k)!}\right) \end{align*}\]

这样就是标准的卷积了。

有标号毛毛虫计数

考虑毛毛虫的虫节，定义它为关键链上的一个点与其一级邻域中非关键点构成的整体。

若一个虫节中存在 $k$ 个点，则方案数显然为 $k$，即选一个点为关键链上的点，因此生成函数为：

\[\hat F_1(x)=\sum_{k\geq 1}k\cdot\frac{x^k}{k!}=\sum_{k\geq 1}\frac{x^k}{(k-1)!}\]

特殊的，对于链两端的虫节，要求它们至少包含 $2$ 个点，因此它俩的生成函数为：

\[\hat F_2(x)=\sum_{k\geq 2}\frac{x^k}{(k-1)!}\]

因此有标号毛毛虫的生成函数为：

\[\begin{align*} \hat G(x)&=\frac{1}{2}(F_2(x)\cdot(\sum_{i\geq k}\hat F_1^k(x))\cdot F_2(x))\\ &=\frac{1}{2}(F_2(x)\cdot\frac{1}{1-\hat F_1(x)}\cdot F_2(x)) \end{align*}\]

然而这个式子并没有计算到菊花的情况，实际答案应为：

\[ans=[x^n]\hat G(x)+n\]

有标号 DAG 计数

设答案 EGF 为 $\hat G(x)$，然后正常考虑通过拓扑序第一层的点构造子问题，通过经典的反演推导，有：

\[[x^n]\hat G(x)=\sum_{i=1}^{n}(-1)^{i-1}\binom{n}{i}2^{i(n-i)}\cdot [x^{n-i}]\hat G(x)\]

这个式子可以仿照前面二分图的的拆分方式得到：

\[\frac{[x^n]\hat G(x)}{2^{\binom{n}{2}}n!}=\sum_{i=1}^{n}\frac{(-1)^{i-1}}{2^{\binom{i}{2}}i!}\cdot\frac{[x^{n-i}]\hat G(x)}{2^{\binom{i-2}{2}}(n-i)!}\]

由于求值依赖先前的项，此处需要使用分治 FFT 解决。

【另一个思路】

设指数型生成函数 $\hat F(x)$ 为：

\[[x^n]\hat F(x)=\frac{(-1)^{n-1}}{2^{\binom{n}{2}}n!}\]

此时根据前面化简拆分得到的卷积形式，有:

\[\hat G(x)\equiv\hat F(x)\hat G(x)-1 \pmod{x^n}\]

因此：

\[\hat G(x)\equiv \frac{1}{\hat F(x)-1} \pmod{x^n}\]

多项式求逆即可。

有标号仙人掌计数

先钦定一个根节点，设有标号有根的仙人掌图的 EGF 为 $\hat G(x)$。

考虑把这个根拆掉之后分出来的子问题，此时考查与根连接的边的情况：

• 仙人掌子连通块以单条边与根节点连接，此时去掉根后这部分连通块的生成函数依然是 $\hat G(x)$。
• 仙人掌子连通块中的一个环套住了根节点，此时去掉根后这部分连通块是若干仙人掌串成的一条链，因此生成函数是 $\frac{1}{2}\sum_{k\geq 2}\hat G^k(x)$。

这些连通块可以组合起来，因此可以列出方程：

\[\hat G(x)=x\exp(\hat G(x)+\frac{1}{2}\sum_{k\geq 2}\hat G^k(x))=x\exp\frac{2\hat G(x)-\hat G^2(x)}{2-2\hat G(x)}\]

列出牛顿迭代的式子解方程：

\[\begin{align*} F(x)&=x\exp\frac{2\hat G(x)-\hat G^2(x)}{2-2\hat G(x)}-\hat G(x)\\ F'(\hat G(x))&=x\left(\exp\frac{2\hat G(x)-\hat G^2(x)}{2-2\hat G(x)}\right)'-1\\ &=x\left(\exp \frac{2\hat G(x)-\hat G^2(x)}{2\hat G(x)-2}\right)\left(\frac{2\hat G(x)-\hat G^2(x)}{2-2\hat G(x)}\right)-1\\ &=x\left(\exp\frac{2\hat G(x)-\hat G^2(x)}{2-2\hat G(x)}\right)\left(\frac{(2-2\hat G(x))^2+2(2\hat G(x)+\hat G^2(x))}{(2-2\hat G(x))^2}\right)-1 \end{align*}\]

然后可以换元，令 $A(x)=2\hat G(x)-\hat G^2(x)$，$B(x)=2-2\hat G^2(x)$，得：

\[F'(\hat G(x))=x\left(\exp\frac{A(x)}{B(x)}\right)\left(\frac{B^2(x)+2A(x)}{B^2(x)}\right)-1\]

然后得到牛顿迭代的式子：

\[\begin{align*} \dot G(x)&\equiv\hat G(x)-\frac{F(\hat G(x))}{F'(\hat G(x))} \pmod{x^{2n}}\\ &\equiv\hat G(x)-\frac{x\left(\exp \frac{A(x)}{B(x)}\right)-\hat G(x)}{x\left(\exp\frac{A(x)}{B(x)}\right)\left(\frac{B^2(x)+2A(x)}{B^2(x)}\right)-1}\pmod{x^{2n}} \end{align*}\]

有标号强连通分量计数

[清华集训 2014] 主旋律！（其实条件不一样。）

同样设答案的 EGF 为 $\hat G(x)$。考虑一般有标号有向图个数 $a_n$，那么将所有强连通分量缩点，套进 DAG 的那个反演式子，即：

\[\begin{align*} a_n&=\sum_{i=1}^{n}2^{i(n-i)}\binom{n}{i}a_{n-i}\sum_{k=1}^{i}\frac{(-1)^{k+1}}{k!}\sum_{\sum_{j}^{k}=i}\binom{i}{s_1,s_2,\dots,s_k}\prod_{j}^{k}[x^{s_j}]\hat G(x)\\ &=\sum_{i=1}^{n}2^{i(n-i)}\binom{n}{i}a_{n-i}\cdot i!\cdot [x^i](\sum_{k\geq 1}\frac{(-1)^{k+1}\hat G^k(x)}{k!})\\ &=\sum_{i=1}^{n}2^{i(n-i)}\binom{n}{i}a_{n-i}\cdot i!\cdot[x^i](1-\exp(-\hat G(x)))\\ \end{align*}\]

接下来需要凑一个卷积形式。

先根据以上式子得出：

\[\frac{a_n}{n!}=\sum_{i=1}^{n}\frac{2^{i(n-i)}a_{n-i}}{(n-i)!}\cdot[x^i](1-\exp(1-\hat G(x)))\]

依然考虑恒等式：

\[k(n-k)=\binom{n}{2}-\left(\binom{k}{2}+\binom{n-k}{2}\right)\]

于是有：

\[\begin{align*} \frac{a_n}{n!}&=\sum_{i=1}^{n}\frac{2^{\binom{n}{2}}\cdot2^{-\binom{i}{2}}\cdot2^{-\binom{n-i}{2}}\cdot a_{n-i}}{(n-i)!}\cdot[x^i](1-\exp(1-\hat G(x)))\\ \frac{a_n}{n!\cdot 2^{\binom{n}{2}}}&=\sum_{i=1}^{n}\frac{a_{n-i}}{(n-i)!2^{\binom{n-i}{2}}}\cdot\frac{[x^i](1-\exp(-\hat G(x)))}{2^{\binom{i}{2}}} \end{align*}\]

显然 $a_n=2^{n(n-1)}$，然后多项式全家桶计算一下即可。

有标号点双连通分量计数

我不会。

有标号边双连通分量计数

我不会。