题意
给定 \(N\) 个带有若干洞的节点，其中第 \(i\) 个点上有 \(d_i\) 个洞。
先可以在两个不同的节点的洞之间连边，一个洞最多连一条边，求使得最终形成的图是一棵树的方案数，对 \(998244353\) 取模。
洞之间相互区分，两个方案不同当且仅当存在一条边在两个方案中的连的洞不同。
- \(2 \le N \le 2 \times 10^5\)
- \(1 \le d_i < 998244353\)
题解
首先设 \(S = \sum d_i\)，那么首先考虑 \(S \ge 2 \left(N - 1\right)\) 的情况，即一定有解的情况。
考虑组成一棵树的过程，可以从每个节点的父边入手，考虑对于每个节点，钦定一个特殊洞，使得其连向父亲节点。
那么我们每次操作可以转化为选择一个特殊洞，再选择一个非特殊洞，使得其相连。
可以发现每次操作后联通块数量一定会减少，在仅剩 \(2\) 个联通块时我们可以使其两个特殊洞相连，进而确定方案。因此我们只需要操作 \(N - 2\) 次。
考虑如何计算方案数。首先钦定特殊洞的方案数显然为 \(\prod d_i\)。对于第 \(i\) 次选择，我们可以从 \(N - i + 1\) 个特殊洞中选择一个，从 \(S - N - i + 1\) 个非特殊洞中选择一个，因此方案数为 \(\left(N - i + 1\right) \times \left(S - N - i + 1\right)\)。
因此可以得出总方案数：
\[\prod d_i \times \prod\limits_{i = 1}^{N - 2} \left(N - i + 1\right) \times \left(S - N - i + 1\right)
\]
即
\[\prod d_i \times \prod\limits_{i = 0}^{N - 3} \left(S - N - i\right) \times N^{\underline{N - 2}}
\]
发现每个节点被选择的顺序是不影响最终的方案的，但是被计算了多次，考虑除去这个影响。
因此最终答案为：
\[\prod d_i \times \prod\limits_{i = 0}^{N - 3} \left(S - N - i\right)
\]
可以发现，若 \(S < 2 \left(N - 1\right)\)，那么上式的值一定为 \(0\)，于实际相符，因此直接计算上式的值即可。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
namespace MODINT {
constexpr valueType MOD = 998244353;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
constexpr valueType Inv2 = (MOD + 1) / 2;
}// namespace MODINT
using namespace MODINT;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
valueType ans = 1, S = 0;
ValueVector D(N);
for (auto &iter : D) {
std::cin >> iter;
Mul(ans, iter);
Inc(S, iter);
}
for (valueType i = 0; i <= N - 3; ++i)
Mul(ans, sub(S, N + i));
std::cout << ans << std::endl;
return 0;
}