没做出来。
考虑求出方案数后除以 \(m^i\) 求出概率。
设 \(U = \{1, 2, ..., n\}\)。
因为题目限制了加几条边，不妨设 \(f_{i, S}\) 为，加了 \(i\) 条边，\(S\) 形成森林且 \(U \setminus S\) 没有边的方案数。
转移枚举子集 \(T\)，钦定 \(T\) 为树，设 \(T\) 为树的方案数为 \(g_T\)，那么 \(f_{i, S} = \sum\limits_{T \subseteq S \land T \neq \varnothing} f_{i - (|T| - 1), S \setminus T} \times g_T\)。
考虑求 \(g_S\)。枚举一条边断开即可。所以枚举 \(T \subset S\)，那么 \(T\) 和 \(S \setminus T\) 都要是树，并且还可以加一条 \(T\) 和 \(S \setminus T\) 之间的边，为了避免算重除以 \(2 (|S| - 1)\)。所以 \(g_S = \frac{1}{2 (|S| - 1)} \times \sum\limits_{T \subset S} g_T \times g_{S \setminus T} \times F(T, S \setminus T)\)，其中 \(F(T, S \setminus T)\) 为两个端点分别在 \(T, S \setminus T\) 中的边数。
\(F(T, S \setminus T)\) 可以容斥求。设 \(h_S\) 为 \(S\) 内部的边数，那么 \(F(T, S \setminus T) = h_S - h_T - h_{S \setminus T}\)。
因为这样求出来的 \(f_{i, U}\) 没有规定加边顺序，所以答案要乘上 \(i!\)。最后 \(i\) 的概率即为 \(\frac{f_{i, U} \times i!}{m^i}\)。
code
// Problem: Ex - We Love Forest
// Contest: AtCoder - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）
// URL: https://atcoder.jp/contests/abc253/tasks/abc253_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 16;
const int maxm = (1 << 14) + 50;
const ll mod = 998244353;
ll n, m, f[maxn][maxm], g[maxm], h[maxm], inv[maxm], fac[maxm];
pii E[maxm];
void solve() {
inv[1] = 1;
for (int i = 2; i < maxm; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
fac[0] = 1;
for (int i = 1; i < maxm; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld", &E[i].fst, &E[i].scd);
--E[i].fst;
--E[i].scd;
int u = E[i].fst, v = E[i].scd;
for (int S = 1; S < (1 << n); ++S) {
if ((S & (1 << u)) && (S & (1 << v))) {
++h[S];
}
}
}
for (int i = 0; i < n; ++i) {
g[1 << i] = 1;
}
for (int S = 1; S < (1 << n); ++S) {
for (int T = (S - 1) & S; T; T = (T - 1) & S) {
int U = S ^ T;
g[S] = (g[S] + g[T] * g[U] % mod * (h[S] - h[T] - h[U] + mod + mod) % mod) % mod;
}
int cnt = __builtin_popcount(S);
if (cnt > 1) {
g[S] = g[S] * inv[2 * (cnt - 1)] % mod;
}
}
for (int S = 0; S < (1 << n); ++S) {
f[0][S] = 1;
}
ll pw = 1, P = inv[m];
for (int i = 1; i < n; ++i) {
for (int S = 1; S < (1 << n); ++S) {
for (int T = S; T; T = (T - 1) & S) {
int e = __builtin_popcount(T) - 1;
if (i < e || ((~T) & lowbit(S))) {
continue;
}
int U = S ^ T;
f[i][S] = (f[i][S] + f[i - e][U] * g[T] % mod) % mod;
}
}
pw = pw * P % mod;
printf("%lld\n", f[i][(1 << n) - 1] * fac[i] % mod * pw % mod);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}