自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:09:06，当前版本为作者最后更新于2025-01-31 17:43:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于一个点 $u$，我们将它的每个连通块个数 $a_{u,i}$ 视为一个接口，称其大小为对应的 $a$ 值。那么你容易发现，两个接口可以用一条边连起来，当且仅当接口大小相加为 $n$。并且，一个点的接口大小总和为 $n-1$。

你发现叶子是最特殊的，因为它必然只有一个大小为 $n-1$ 的接口，那么叶子必然会把所有大小为 $1$ 的接口全部匹配掉。这个方案数是好算的，相当于每个其他点选固定个数的叶子挂上去，组合数算一算即可。那么大小为 $1,n-1$ 的接口就被排除掉了。

有啥用呢？你还会发现更加奇妙的事情。考虑一个节点若有大小为 $n-2$ 的接口会发生什么？因为接口大小总和为 $n-1$，那么剩下的那个接口大小必定为 $1$，已经匹配掉了。所以我们可以将大小 $n-2$ 的接口再次视为叶子接口，与所有大小为 $2$ 的接口匹配。更近一步地，假设当前我们将所有 $\le k$ 的接口匹配完毕了，那么删掉这些接口后，大小为 $n-k$ 的接口必然是叶子接口！

从小到大枚举 $k$ 即可。剩下一个 corner case 就是 $n$ 为偶数时 $k=n/2$ 的情况。不过大小都为 $n/2$ 了，说明砍掉接口这条边，树会恰好分成大小相等的两半。这个的方案数显然为 $1$，所以不用管就好了。

有更聪明的实现方法，因为对于大小 $<\lfloor(n+1)/2\rfloor$ 的接口，其贡献都是个数的阶乘倒数，反之贡献为个数的阶乘，可以边读入来算。时间复杂度 $O(n)$。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e5 + 10;
const int mod = 998244353;

inline 
int qpow(int b, int p) {
	int res = 1;
	for (; p; p >>= 1, b = (ll)b * b % mod) if (p & 1) res = (ll)res * b % mod;
	return res;
}

int n, m, a[MAXN], c1[MAXN], c2[MAXN], fac[MAXN], ifac[MAXN], ans = 1;

int main() {
	scanf("%d", &n), *fac = 1;
	for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n; i; i--) ifac[i - 1] = (ll)ifac[i] * i % mod;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &m);
		for (int j = 1; j <= m; j++) scanf("%d", &a[j]), c1[a[j]]++, c2[a[j]]++;
		for (int j = 1; j <= m; j++) {
			if (a[j] < (n + 1) / 2) ans = (ll)ans * ifac[c1[a[j]]] % mod;
			c1[a[j]] = 0;
		}
	}
	for (int i = n / 2 + 1; i < n; i++) ans = (ll)ans * fac[c2[i]] % mod;
	printf("%d", ans);
}

做完这题可以去做猫娘。