ARC106F Figures 题解

· · 题解

Figures

题目链接。cnblogs。luogu。

Problem

有 N 个点，每个点有 d_i 个互不相同、可被区分的孔，每次可以选择两个不同点，连接两个未被连接过的孔，有多少种方案使得最后形成一棵树。合法方案中可以不把孔填满。

Sol

模拟赛题。

由于除根节点外每个点只有一个父亲节点，考虑从这里入手。

给每个点指定一个特殊点，让这个特殊点连向它的父亲节点的非特殊点。此时只有根节点没有特殊点，可随便指定一个特殊点，因为是无根树，且根节点最后是会与某个节点留下来的。指定特殊点的方案数易知：\prod \limits_{i = 1}^{n} d_i。

令 S = \sum d_i，因为每个点是由特殊点连向非特殊点，又不能重复经过点，故需再乘上 \prod \limits_{i = 0}^{n - 3}(S - n - i)。

所以最后的答案为 \prod d_i \times\prod(S - n - i)。

时间复杂度线性。

上面的做法可能不是很好想到？下面是一个套路的代数推导的做法：

记第 i 个点有 c_i 个孔。\binom{n}{a_1, a_2, a_3, \cdots, a_m} 表示多重集组合数。a^{\underline b} 表示 a 的 b 次下降幂，即 \frac{a!}{(a - b)!}。

若知道度数序列 d，则方案数为 \binom{n - 2}{d_1 - 1, d_2 - 1, \cdots, d_n - 1} \times \prod c_i^{\underline{d_i}}。

于是最后的方案数为：

\sum\limits_{|d| = n, \sum d_i = 2n - 2, \forall i\in[1, n], d_i > 0} \binom{n - 2}{d_1 - 1, d_2 - 1, \cdots, d_n - 1} \prod\limits_{i = 1}^{n} c_i^{\underline{d_i}}

然后就是正常的推式子：

(n - 2)! \times\sum\limits_{|d| = n, \sum d_i' = n - 2, \forall i\in[1, n], d_i \ge 0} \prod \frac{c_i!}{d_i'!\times (c_i - d_i' - 1)!} \\ = (n - 2)! \times (\prod c_i) \times \sum\limits_{|d| = n, \sum d_i' = n - 2, \forall i\in[1, n], d_i \ge 0} \prod \binom{c_i - 1}{d_i'}

发现后面的那部分其实就是多元情况的范德蒙德卷积，记 S = \sum (c_i - 1)，：为

(n - 2)! \times (\prod c_i) \times \binom{S - n}{n - 2} \\ (S - n)^{\underline{n - 2}} \times \prod c_i

Update on 25.02.24：增加代数推导的做法。

Code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0);
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 1e9, infi32 = 2147483647, mod = 998244353;
const ll INF = 1e18;

const int N = 2e5 + 10;
int n;
int d[N];

int main () {
    ios
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> d[i];
    int sum = 0, ans = 1;
    for (int i = 1; i <= n; i++) sum = (sum + d[i]) % mod, ans = 1ll * ans * d[i] % mod;
    for (int i = sum - n * 2 + 3; i <= sum - n; i++) ans = 1ll * ans * (i + mod) % mod;
    cout << ans << "\n";
    return 0;
}