专栏文章

猕猴桃 T4

RRegister_int-std=c++14
P11645题解参与者 10已保存评论 10

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
10 条
当前快照
1 份
快照标识符
@miqd9zc8
此快照首次捕获于
2025/12/04 02:55
3 个月前
此快照最后确认于
2025/12/04 02:55
3 个月前
查看原文
对于一个点 uu，我们将它的每个连通块个数 au,ia_{u,i} 视为一个接口，称其大小为对应的 aa 值。那么你容易发现，两个接口可以用一条边连起来，当且仅当接口大小相加为 nn。并且，一个点的接口大小总和为 n−1n-1。
你发现叶子是最特殊的，因为它必然只有一个大小为 n−1n-1 的接口，那么叶子必然会把所有大小为 11 的接口全部匹配掉。这个方案数是好算的，相当于每个其他点选固定个数的叶子挂上去，组合数算一算即可。那么大小为 1,n−11,n-1 的接口就被排除掉了。
有啥用呢？你还会发现更加奇妙的事情。考虑一个节点若有大小为 n−2n-2 的接口会发生什么？因为接口大小总和为 n−1n-1，那么剩下的那个接口大小必定为 11，已经匹配掉了。所以我们可以将大小 n−2n-2 的接口再次视为叶子接口，与所有大小为 22 的接口匹配。更近一步地，假设当前我们将所有 ≤k\le k 的接口匹配完毕了，那么删掉这些接口后，大小为 n−kn-k 的接口必然是叶子接口！
从小到大枚举 kk 即可。剩下一个 corner case 就是 nn 为偶数时 k=n/2k=n/2 的情况。不过大小都为 n/2n/2 了，说明砍掉接口这条边，树会恰好分成大小相等的两半。这个的方案数显然为 11，所以不用管就好了。
有更聪明的实现方法，因为对于大小 <⌊(n+1)/2⌋<\lfloor(n+1)/2\rfloor 的接口，其贡献都是个数的阶乘倒数，反之贡献为个数的阶乘，可以边读入来算。时间复杂度 O(n)O(n)。
CPP
#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);
}
做完这题可以去做猫娘。

评论

共 10 条评论，欢迎与作者交流。

正在加载评论...