526互联

CODE FESTIVAL 2017 Elimination Tournament Round 3 F Unicyclic Graph Counting

发布时间 2023-09-27 10:43:02作者: zltzlt

洛谷传送门

AtCoder 传送门

看到和度数有关的（基环）树计数，可以想到 Prufer 序。

如果要计数一棵树，那么答案就是 \(\binom{n - 2}{d_1 - 1, d_2 - 1, \ldots, d_n - 1}\)。因为度数为 \(d\) 的点在 Prufer 序中恰好出现 \(d - 1\) 次。

但是现在是基环树。特判掉 \(\forall i \in [1, n], d_i = 2\)，然后考虑把环缩成一个点。求树的 Prufer 序最后会剩下两个点，那么这里会剩下一个环往外连一个单点。

设环长为 \(k\)，若已经确定了环上点的标号集合，那么方案数为 \(\frac{(k - 1)!}{2}\)。\((k - 1)!\) 是长度为 \(k\) 的圆排列数，乘 \(\frac{1}{2}\) 是减掉翻转同构的环。

那么有 \(k - 1\) 个点在 Prufer 序中出现 \(d_i - 2\) 次，\(1\) 个特殊点（环上连了一个单点的点）在 Prufer 序中出现 \(d_i - 3\) 次，其余点（树点）出现 \(d_i - 1\) 次，Prufer 序长度为 \(n - |S| - 1\)。

那么若确定环点集合 \(S\)，特殊点为 \(u\)，那么答案为：

\[\frac{(n - |S| - 1)!}{(\prod\limits_{i \in S \land i \ne u} (d_i - 2)!) (d_u - 3)! (\prod\limits_{i \notin S} (d_i - 1)!)} \times \frac{(|S| - 1)!}{2} \]

考虑 dp 出 \(\sum\limits_{S, u} \frac{1}{(\prod\limits_{i \in S \land i \ne u} (d_i - 2)!) (d_u - 3)! (\prod\limits_{i \notin S} (d_i - 1)!)}\)。设 \(f_{i, j, 0/1}\) 表示考虑了 \(i\) 个点，其中有 \(j\) 个环点，有没有出现特殊点，前面式子之和。

转移就讨论第 \(i\) 个点是环点还是特殊点还是树点即可。答案为：

\[\sum\limits_{i = 3}^{n - 1} (n - i - 1)! f_{n, i, 1} \times \frac{(i - 1)!}{2} \]

时间复杂度 \(O(n^2)\)。

code 
// Problem: F - Unicyclic Graph Counting
// Contest: AtCoder - CODE FESTIVAL 2017 Elimination Tournament Round 3 (Parallel)
// URL: https://atcoder.jp/contests/cf17-tournament-round3-open/tasks/asaporo2_f
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 310;
const ll mod = 1000000007;

ll n, a[maxn], fac[maxn], inv[maxn], ifac[maxn], f[maxn][maxn][2];

inline void upd(ll &x, ll y) {
	((x += y) >= mod) && (x -= mod);
}

void solve() {
	scanf("%lld", &n);
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[1] = 1;
	for (int i = 2; i <= n; ++i) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	}
	ifac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		ifac[i] = ifac[i - 1] * inv[i] % mod;
	}
	bool flag = 1;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		flag &= (a[i] == 2);
	}
	if (flag) {
		printf("%lld\n", fac[n - 1] * inv[2] % mod);
		return;
	}
	f[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			for (int k = 0; k <= 1; ++k) {
				if (!f[i - 1][j][k]) {
					continue;
				}
				upd(f[i][j][k], f[i - 1][j][k] * ifac[a[i] - 1] % mod);
				if (a[i] >= 2) {
					upd(f[i][j + 1][k], f[i - 1][j][k] * ifac[a[i] - 2] % mod);
				}
				if (a[i] >= 3 && !k) {
					upd(f[i][j + 1][1], f[i - 1][j][k] * ifac[a[i] - 3] % mod);
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 3; i < n; ++i) {
		upd(ans, f[n][i][1] * fac[i - 1] % mod * inv[2] % mod * fac[n - i - 1] % mod);
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}