题解 P5828 【边双连通图计数】
iostream
2019-12-18 21:01:26
## 前置技能：无向连通图计数
设有标号无向图的 egf 为 $F(x)=\sum_{i=0}^\infty \frac{f_ix^i}{i!}$，容易知道 $f_i=2^{n\choose 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_{n\ge 1} \frac{b_nx^n\exp(nD(x))}{n!}=B(x\exp(D(x)))$$
设 $F(x)=x\exp(D(x))$ 则 $D(x)=B(F(x))$；
两边对 $F(x)$ 作复合逆得 $B(x)=D(F^{-1}(x))$。
有扩展拉格朗日反演公式如下：
$$[x^n]A(B^{-1}(x))=\frac{1}{n} [x^{n-1}]A'(x)(\frac{x}{B(x)})^n$$
代入可得 $[x^n]B(x)=\frac{1}{n} [x^{n-1}]D'(x)(\frac{x}{F(x)})^n$，继续化简可得
$$[x^n]B(x)=\frac{1}{n} [x^{n-1}]D'(x)\exp(-nD(x))$$
我们可以在 $O(n\log n)$ 的时间复杂度求得 $B(x)$ 的一项系数，注意是有根边双的 egf，最后要乘一个 $n!$ 和除以一个 $n$。
```cpp
//多项式模板略去
void init()
{
F.resize(n+1);
for(int i=0;i<F.size();++i)F[i]=power(2,(ll)i*(i-1)/2%(mod-1),ifac[i]);
D=Ln(F);
for(int i=0;i<D.size();++i)Mul(D[i],i);
G=Deriv(D);
}
// B(x)->有根边双
// D(x)=B(xexp(D(x)))
// [x^n]B(x) = \frac{1}{n}[x^{n-1}]D'(x) (1/exp(D))^n
int calc(int n)
{
Poly C(D.begin(),D.begin()+n),L(G.begin(),G.begin()+n);
for(int i=0;i<C.size();++i)Mul(C[i],mod-n);
C=Exp(C)*L;
return mul(inv[n],C[n-1]);
}
int main()
{
init();
scanf("%d",&n);
ans=(ll)calc(n)*fac[n-1]%mod; //n!是因为egf, 除去n是因为有根
printf("%d\n",ans);
}
```