前几天学习了一下扩展拉格朗日反演（因为模拟赛考了），推了一下点双和边双图的计数，记录一下。
前置技能：无向连通图计数
设有标号无向图的 egf 为 (F(x)=sum_{i=0}^infty frac{f_ix^i}{i!})，容易知道 (f_i=2^{nchoose 2})，则有标号连通无向图的 egf 满足 (G=ln F)。
边双连通图
首先设有根连通无向图的指数生成函数是 (D(x))，有根边双连通图的指数生成函数是 (B(x))。
用 (B) 来表示 (D)：假设根所在边双大小 (n)，其egf为 (frac{b_nx^n}{n!})，而对于其相邻的边，对于其中一条边，它挂着一个连通无向图，接在边双的任意一个点上，所以得到它的egf为 (nD(x))；若干边自由排列（这里也可以理解成集合的组合），故邻边的egf是 (exp(nD(x)))。
枚举大小求和得 $$D(x)=sum_{nge 1} frac{b_nx^nexp(nD(x))}{n!}=B(xexp(D(x)))$$
设 (F(x)=xexp(D(x))) 则 (D(x)=B(F(x)))；
两边对 (F(x)) 作复合逆得 (B(x)=D(F^{-1}(x)))。
有扩展拉格朗日反演公式如下：
代入可得 ([x^n]B(x)=frac{1}{n} [x^{n-1}]D'(x)(frac{x}{F(x)})^n)，继续化简可得
我们可以在 (O(nlog n)) 的时间复杂度求得 (B(x)) 的一项系数，注意是有根边双的egf，最后要乘一个 (n!) 和除以一个 (n)。
点双连通图
依然设有根连通无向图的指数生成函数是 (D(x))。
点双肯定从点考虑，分析一下一个连通图点双分解的形态，根节点被若干个点双包含。
设 (b_i) 为 (i) 个点的点双图数目。
一个包含根的点双，除了根另有 (n) 个点，这 (n) 个点都挂着有根连通无向图，可得这一群点的 egf 为 (sum_{nge 1} b_{n+1} frac{D(x)^n}{n!})。
将点双自由排列（这里也可以理解成集合的组合），要选根再乘上一个 (x)，得到
设 (B(x)=sum_{i=1}^infty b_{i+1}frac{x^i}{i!})，化简得到
继续变换得 (x=frac{D(x)}{exp B(D(x))}
ightarrow D^{-1}(x)=frac{x}{exp B(x)})
因此，(B(x)=ln frac{x}{D^{-1}(x)})，复合逆多项式是不能直接求出来的。
记辅助函数 (G(x)=ln frac{D(x)}{x}) 则 (B(x)=G(D^{-1}(x)))。
代入扩展拉格朗日反演：
我们要求的即 (b_n=[x^{n-1}]B(x)) 可以单次 (O(nlog n)) 计算。
注意要特判掉 (n=1) 的情况。
笔者注（2020.3.20）
注意这里 (b_n) 不强调有根，仔细考虑后究其原因如下：
首先，有根意味着我们考虑当前这个根节点的标号，标号为 (1sim n) 算作不同的。
在边双连通图计数中，我们直接考虑了根所在的边双，给根节点安排一个标号是必要的。
在点双连通图计数中，我们考虑的是每个点双除去根节点以外的标号顺序，给根节点安排不同的标号显然毫无意义。而我们最后乘上一个 (x)，根据 egf 的定义，相当于解决了给根节点安排了序号的问题。