Guest User

Untitled

a guest
Feb 1st, 2025
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.66 KB | None | 0 0
  1. (由于技术原因,联网搜索暂不可用)
  2.  
  3. 为了解决这个问题,我们需要根据给定的每个节点删除后的连通块信息,确定可能的树结构数量。我们需要确保每个节点的度数与其删除后的连通块数量一致,并且满足树的结构条件。
  4.  
  5. ### 方法思路
  6. 1. **度数确认**:每个节点的度数等于其删除后的连通块数量。
  7. 2. **生成树计数**:使用组合数学中的生成树计数公式,计算可能的树结构数量。公式为:
  8. \[
  9. \text{答案} = \frac{(n-2)!}{\prod_{i=1}^{n} (d_i - 1)!} \mod 998244353
  10. \]
  11. 其中,\(d_i\) 是第 \(i\) 个节点的度数。
  12.  
  13. ### 解决代码
  14. ```cpp
  15. #include <bits/stdc++.h>
  16. using namespace std;
  17.  
  18. using ll = long long;
  19. const int MOD = 998244353;
  20. const int MAXN = 300010;
  21.  
  22. ll fact[MAXN], inv_fact[MAXN];
  23.  
  24. ll pow_mod(ll a, ll b) {
  25. ll res = 1;
  26. while (b > 0) {
  27. if (b % 2 == 1) res = res * a % MOD;
  28. a = a * a % MOD;
  29. b /= 2;
  30. }
  31. return res;
  32. }
  33.  
  34. void precompute() {
  35. fact[0] = 1;
  36. for (int i = 1; i < MAXN; i++) {
  37. fact[i] = fact[i-1] * i % MOD;
  38. }
  39. inv_fact[MAXN-1] = pow_mod(fact[MAXN-1], MOD-2);
  40. for (int i = MAXN-2; i >= 0; i--) {
  41. inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
  42. }
  43. }
  44.  
  45. int main() {
  46. ios::sync_with_stdio(false);
  47. cin.tie(0);
  48.  
  49. precompute();
  50.  
  51. int n;
  52. cin >> n;
  53.  
  54. ll denominator = 1;
  55. int sum_d = 0;
  56. for (int i = 0; i < n; i++) {
  57. int d;
  58. cin >> d;
  59. sum_d += d;
  60. vector<int> parts;
  61. for (int j = 0; j < d; j++) {
  62. int x;
  63. cin >> x;
  64. parts.push_back(x);
  65. }
  66. denominator = denominator * inv_fact[d-1] % MOD;
  67. }
  68.  
  69. if (n == 1) {
  70. cout << "1\n";
  71. return 0;
  72. }
  73. if (sum_d != 2*(n-1)) {
  74. cout << "0\n";
  75. return 0;
  76. }
  77.  
  78. if (n-2 < 0) {
  79. cout << "0\n";
  80. return 0;
  81. }
  82. ll numerator = fact[n-2];
  83. ll res = numerator * denominator % MOD;
  84. cout << res << '\n';
  85.  
  86. return 0;
  87. }
  88. ```
  89.  
  90. ### 代码解释
  91. 1. **预计算阶乘和逆元**:使用快速幂和费马小定理预计算阶乘及其逆元,以便快速计算组合数。
  92. 2. **读取输入**:读取每个节点的度数及其对应的连通块大小。
  93. 3. **计算分母**:分母是所有节点度数减一的阶乘的乘积的逆元。
  94. 4. **计算分子**:分子是 \((n-2)!\)。
  95. 5. **计算结果**:将分子和分母结合,计算最终结果并取模。
  96.  
  97. 这种方法确保了在给定约束条件下的高效计算,能够处理较大的数据范围。
Add Comment
Please, Sign In to add comment