题解 P5828 【边双连通图计数】

· · 题解

前置技能：无向连通图计数

设有标号无向图的 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。

//多项式模板略去
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);
}