Luogu5828 边双连通图计数

题面

简化题意

求 $n$ 个点的有标号边双连通图的个数，对 $998244353$ 取模。

$n\leq 10^5$。

题解

因为直接求边双连通图数量很麻烦，不妨考虑求出连通无向图的总数，再减去有割边的无向连通图个数。

不难发现一个无向连通图有割边，那么它边双缩点之后一定是一颗树。设无向图中有 $m$ 个边双连通分量，大小分别为 $a_1,a_2,\cdots,a_m$。根据 CF156D 这个题的结论，可以用 Prufer 序列（可以参考 xht 的题解）证明，总点数为 $n$ 的 $m$ 个连通块，添加 $m-1$ 条使原图连通的方案数为 $n^{m-2}\prod_{i=1}^m a_i$。

枚举连通块的时候，考虑每个连通块内部是一个边双，也就是求出一个 $a_i$ 个点的有标号无向边双连通图数量，这和这个题本身是一样的，确切地说这是原题的形式相同的子问题。因此再把 $a_i$ 代进来容斥，用 $a_i$ 个节点的无向连通图数量减去无向非边双连通图数量……一直容斥下去，因此原方案数还要带一个 $-1$ 的容斥系数。

还有一个感性的理解（口糊的，不知道对错，大家看一看做个乐子），如果对于一个连通块，单纯地只枚举它是一个连通块，那么大小为 $k$ 的连通块可能本身不是边双，而是 $p$ 条割边连接的连通图，而这种（不合法）情况刚好就是大小为 $k+p$ 的连通块中的合法方案，因此对于所有的 $p$，要减掉 $k+p$ 中合法的方案，而大小为 $k+p$ 的连通块中也可能算出不合法方案……而大小 $1$ 的连通块一定是边双，无需考虑不合法问题。

Anyway，需要带上 $-1$ 的容斥系数，即 $(-1)^{m+1} n^{m-2}\prod_{i=1}^m a_i$。把这个东西拆一下得到：

$-\frac{1}{n^2}\prod_{i=1}^m (-na_i)$

由 P4841，有标号连通图的 EGF 是可以求得的，根据 OI-Wiki 的证明可以得到它为有标号无向图的 EGF 求个 $\ln$。设有标号连通图的 EGF 为 $\operatorname{F}(x)$。代入式子：

$\text{let } \operatorname{G}_i=-ni\operatorname{F}_i$

为什么要多乘上一个 $i$？个人第一想法是方便直接 $\exp$。由：

$\exp(\operatorname{G}(x)) = \sum \frac{\operatorname{G}^i(x)}{i}$

则答案可以表示为：

$ans = [x^n] - \frac{n!}{n^2}\exp(\operatorname{G(x)})$

代码

主函数代码：

fac[0]=1;
for(register int i=1;i<=N;++i)
    fac[i]=fac[i-1]*i%mod;
inv[N]=mi(fac[N]);
for(register int i=N-1;i>=0;--i)
    inv[i]=inv[i+1]*(i+1)%mod;
for(register int T=5,tmp;T>0;--T){
    n=read(),tmp=1;
    while(tmp<=n) tmp<<=1;
    for(register int i=0;i<=n;++i)
        f[i]=mi(2,i*(i-1)/2)*inv[i]%mod;
    DXS::init(tmp),
    DXS::Ln(f,g,tmp);
    for(register int i=0;i<=n;++i)
        f[i]=(mod-g[i]*i%mod*n%mod)%mod;
    memset(g,0,sizeof(g));
    DXS::Exp(f,g,tmp);
    write((mod-g[n])*mi(n*n%mod)%mod*fac[n]%mod),putchar('\n');
}