自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:14:44，当前版本为作者最后更新于2021-08-28 20:06:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家的做法都用了拉反，给个不用拉反的做法。

考虑容斥：钦定边集 $S$，满足 $S$ 中的边都是割边。

最终的图一定是若干个联通块由 $S$ 中的边连成的。若把联通块看做点，那么最终的图就是一颗树。

直接做不好做，因此更换枚举顺序。先枚举连通块（设大小分别为 $a_1,a_2,...,a_m$），再枚举 $S$。根据一个经典结论，取 $S$ 的方案数是 $n^{m-2} \prod a_i$。带上容斥系数就是 $-\frac{1}{n^2} \prod (-na_i)$。

设有标号连通图的 $\rm EGF$ 为 $H$。那么设 $G(x)$ 满足 $G_i = -niH_i$，答案就是 $[x^n]-\frac{n!}{n^2} e^{G}$。

核心代码：

cin >> n;
poly F (n + 1);
F[0] = 1;
L(i, 1, n) F[i] = (ll) F[i - 1] * qpow (2, i - 1) % mod * inv[i] % mod;
F = F.Ln();
L(i, 1, n) F[i] = mod - (ll) F[i] * i % mod * n % mod;
F = F.Exp();
cout << (ll) (mod - F[n]) * inv[n] % mod * fac[n - 1] % mod << "\n";