526互联

AtCoder Regular Contest 106 F Figures

发布时间 2023-04-17 20:42:37作者: zltzlt

洛谷传送门

AtCoder 传送门

晚自习的时候胡出来的做法（（（

首先你会发现题目等价于求 \(\sum\limits_{(\sum\limits_{i=1}^n a_i) = 2(n-1) \land \forall i \in [1,n], 1 \le a_i \le d_i} \prod\limits_{i=1}^n \dfrac{d_i!}{(d_i - a_i)!}\)。翻译一下就是枚举每个点的度数 \(a_i\)（一个结论是当度数总和 \(= 2(n-1)\) 并且每个点的度数都为正整数时一定能构造出合法的树），然后乘上对应的有序选择点内的洞的方案。

你会发现如果固定 \(a_i\)，这个东西的组合意义是把 \(\sum\limits_{i=1}^n d_i\) 个数分成 \(n\) 组每组 \(d_i\) 个数，再在每组有序选出 \(a_i\) 个数。\(a_i \ge 1\) 比较烦，不妨整体减 \(1\)，也就是一开始每组先选一个数，这样就变成了 \(a_i \ge 0\)。然后就发现可以把组合并起来考虑，即答案为先在每组中选一个数再在 \(\sum\limits_{i=1}^n (d_i - 1)\) 个数内有序选择 \(\sum\limits_{i=1}^n (a_i - 1) = n - 2\) 个数的方案数，即 \((\prod\limits_{i=1}^n d_i) \dfrac{(\sum\limits_{i=1}^n (d_i - 1))!}{(n-2)!}\)，这个东西可以 \(O(n)\) 计算。

code 
// Problem: F - Figures
// Contest: AtCoder - AtCoder Regular Contest 106
// URL: https://atcoder.jp/contests/arc106/tasks/arc106_f
// Memory Limit: 1024 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 mems(a, x) memset((a), (x), sizeof(a))

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

const int maxn = 200100;
const ll mod = 998244353;

ll n, a[maxn];

void solve() {
	scanf("%lld", &n);
	ll s = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		s += a[i];
	}
	if (s < (n - 1) * 2) {
		puts("0");
		return;
	}
	s -= n;
	ll ans = 1;
	for (int i = 1; i <= n; ++i) {
		ans = ans * a[i] % mod;
	}
	for (int i = 0; i < n - 2; ++i) {
		ans = ans * ((s - i) % mod) % mod;
	}
	printf("%lld\n", ans);
}

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