526互联

AtCoder Beginner Contest 253 Ex We Love Forest

发布时间 2023-06-16 17:34:25作者: zltzlt

洛谷传送门

AtCoder 传送门

没做出来。

考虑求出方案数后除以 \(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;
}