P5828

zhoukangyang · 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";