1 条题解
-
1
题目大意
给定 个 AI,它们之间连成一棵树。对每个节点 ,若删去它,则会分裂成 个连通块,大小分别为:
求所有满足条件的树的数量对 取模的结果。
题目解法
容易发现 为 节点的度数,那么肯定有:
这一步暂时先放着,待会儿用。
接下来设 ,满足 和 有直接连边,那么:
-
当「删去 」时, 所在连通块大小为 。
-
当「删去 」时, 所在连通块大小为 。
在一棵树中,删除 和删除 得到的那两个「含有对方的连通块」实际上是互补的:它们加在一起正好包含整棵树的所有 个节点,但由于「删点」各自去掉了 或 本身,所以这两个连通块在原图里其实是不重叠的。由此可得:
那么我们可以得到一个重要结论:若 和 相邻,则必存在一对 使它们之和等于 。反之,若能在两个点的「子树大小多重集」里分别找到一对数之和为 ,就可以作为一条 到 的边。
我们把节点的所有 收集在一起构成一个大小为 的多重集 。树的每条边都会对应一对 ,此时我们得到「边的集合」,再确保第 个点的度数为 便可求出方案数。
问题:如何求出方案数?
我们先令 为所有 中连通块大小为 的数量, 为删除第 个点时产生的连通块中大小为 的连通块数量,考虑分为两步求解:
-
统计「纯粹的」方案数(不考虑重复):
- 当 时,两者必须一一匹对,所以这里的方案数为 。因为题目保证有解,所以 必然等于 。
- 当 时,我们需要配对 对 ,设 $k = \displaystyle\frac{\text{cnt}_{\frac{n}{2}}}{2}$,那么此时的方案数为:
这些式子相乘即可求出。
-
去除重复的方案:
- 我们发现这个算法会重复计算。举个例子,比如 ,两个 并无顺序可言,无论把「第 个 」匹配给邻居 ,把「第 个 」匹配给邻居 ,都对应一组同样的边 ,只要这两个邻居在最终树中的度数信息等都吻合,就不能算作两种不同的树。
- 为了避免这个问题,我们对于每个节点 ,将答案乘上 即可。
综上,我们的答案可以表示为:
令 为:
$$\left(\prod_{2k < n}\text{cnt}_k!\right) \times \begin{cases}(\frac{\text{cnt}_{\frac{n}{2}}}{2})!!, & n\text{ is even,}\\[6pt]1, & n\text{ is odd.}\end{cases} $$令 为:
$$\prod_{i = 1} ^ n \prod_{x}\left(\text{mult}_{i, x}!\right) $$则答案为 。
复杂度分析
-
时间复杂度:。
-
空间复杂度 。
代码实现
#include <bits/stdc++.h> #define int long long constexpr int N = 1e5 + 6, P = 998244353; int power(int a, int b, int p) { int ans = 1; a %= p; while (b > 0) { if (b & 1) { ans = ans * a % p; } a = a * a % p; b >>= 1; } return ans; } void solve() { int n; std::cin >> n; std::vector<int> d(n + 1, 0); int sum = 0; std::vector<int> freq(n + 1, 0); std::vector<std::unordered_map<int, int>> cont(n + 1); for (int i = 1; i <= n; ++i) { std::cin >> d[i]; sum += d[i]; for (int j = 1; j <= d[i]; ++j) { int sz; std::cin >> sz; ++freq[sz]; ++cont[i][sz]; } } int MAX = 2 * (n - 1); std::vector<int> fact(MAX + 1, 0), ifact(MAX + 1, 0); fact[0] = 1; for (int i = 1; i <= MAX; ++i) { fact[i] = fact[i - 1] * i % P; } ifact[MAX] = power(fact[MAX], P - 2, P); for (int i = MAX - 1; i >= 0; --i) { ifact[i] = ifact[i + 1] * (i + 1) % P; } int m = 1; for (int k = 1; k * 2 < n; ++k) { m = m * fact[freq[k]] % P; } auto so = [&](int x) -> int { int res = fact[x]; res = res * power(power(2, x / 2, P), P - 2, P) % P; res = res * ifact[x / 2] % P; return res; }; if (n % 2 == 0) { int x = freq[n / 2]; m = m * so(x) % P; } int dd = 1; for (int i = 1; i <= n; ++i) { for (auto & kv : cont[i]) { dd = dd * fact[kv.second] % P; } } std::cout << m * power(dd, P - 2, P) % P; } int32_t main() { std::ios::sync_with_stdio(0); std::cin.tie(0), std::cout.tie(0); int t; // std::cin >> t; t = 1; while (t--) { solve(); } return 0; }
-
- 1
信息
- ID
- 113
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 228
- 已通过
- 80
- 上传者