猕猴桃 T4

· · 题解

对于一个点 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);
}

做完这题可以去做猫娘。