Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (由于技术原因,联网搜索暂不可用)
- 为了解决这个问题,我们需要根据给定的每个节点删除后的连通块信息,确定可能的树结构数量。我们需要确保每个节点的度数与其删除后的连通块数量一致,并且满足树的结构条件。
- ### 方法思路
- 1. **度数确认**:每个节点的度数等于其删除后的连通块数量。
- 2. **生成树计数**:使用组合数学中的生成树计数公式,计算可能的树结构数量。公式为:
- \[
- \text{答案} = \frac{(n-2)!}{\prod_{i=1}^{n} (d_i - 1)!} \mod 998244353
- \]
- 其中,\(d_i\) 是第 \(i\) 个节点的度数。
- ### 解决代码
- ```cpp
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- const int MOD = 998244353;
- const int MAXN = 300010;
- ll fact[MAXN], inv_fact[MAXN];
- ll pow_mod(ll a, ll b) {
- ll res = 1;
- while (b > 0) {
- if (b % 2 == 1) res = res * a % MOD;
- a = a * a % MOD;
- b /= 2;
- }
- return res;
- }
- void precompute() {
- fact[0] = 1;
- for (int i = 1; i < MAXN; i++) {
- fact[i] = fact[i-1] * i % MOD;
- }
- inv_fact[MAXN-1] = pow_mod(fact[MAXN-1], MOD-2);
- for (int i = MAXN-2; i >= 0; i--) {
- inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
- }
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- precompute();
- int n;
- cin >> n;
- ll denominator = 1;
- int sum_d = 0;
- for (int i = 0; i < n; i++) {
- int d;
- cin >> d;
- sum_d += d;
- vector<int> parts;
- for (int j = 0; j < d; j++) {
- int x;
- cin >> x;
- parts.push_back(x);
- }
- denominator = denominator * inv_fact[d-1] % MOD;
- }
- if (n == 1) {
- cout << "1\n";
- return 0;
- }
- if (sum_d != 2*(n-1)) {
- cout << "0\n";
- return 0;
- }
- if (n-2 < 0) {
- cout << "0\n";
- return 0;
- }
- ll numerator = fact[n-2];
- ll res = numerator * denominator % MOD;
- cout << res << '\n';
- return 0;
- }
- ```
- ### 代码解释
- 1. **预计算阶乘和逆元**:使用快速幂和费马小定理预计算阶乘及其逆元,以便快速计算组合数。
- 2. **读取输入**:读取每个节点的度数及其对应的连通块大小。
- 3. **计算分母**:分母是所有节点度数减一的阶乘的乘积的逆元。
- 4. **计算分子**:分子是 \((n-2)!\)。
- 5. **计算结果**:将分子和分母结合,计算最终结果并取模。
- 这种方法确保了在给定约束条件下的高效计算,能够处理较大的数据范围。
Add Comment
Please, Sign In to add comment