题目链接：AtCoder Regular Contest 106 F

Takahashi 有 $n$ 个不同的零件和 $n - 1$ 个连接件，第 $i$ 个零件上有 $d_{i}$ 个不同孔。每个连接件可以插入属于不同零件的两个孔，每个孔不能插入多个连接件。现在，Takahashi 需要把用连接件把所有零件连接成一棵树，求出不同的连接方案数，答案对 $998244353$ 取模。

数据范围：$2 \le n \le 2 \times 10 ^{5}$，$1 \le d_{i} < 998244353$。

Solution

根据 Prufer 序列计数：

$$ \begin{align} & \sum_{\sum a_{i} = n - 2} \binom{n - 2}{a_{1}, a_{2}, \ldots, a_{n}} \prod_{i = 1} ^ {n} \binom{d_{i}}{a_{i} + 1} (a_{i} + 1)! \\ = & \sum_{\sum a_{i} = n - 2} \binom{n - 2}{a_{1}, a_{2}, \ldots, a_{n}} \prod_{i = 1} ^ {n} d_{i} ^ {\underline{a_{i} + 1}} \\ = & (n - 2)!\sum_{\sum a_{i} = n - 2} \prod_{i = 1} ^ {n} \frac{d_{i} ^ {\underline{a_{i} + 1}}}{a_{i}!} \end{align} $$

设指数型生成函数 $F_{k}(x)$：

$$ \begin{align} F_{k}(x) & = \sum_{i = 0} ^ {k} \frac{k ^ {\underline{i + 1}}}{i!} x ^ {i} \\ & = \sum_{i = 0} ^ {k} \frac{k!}{(k - i - 1)! \cdot i!} x ^i \\ & = k \sum_{i = 0} ^ {k} \binom{k - 1}{i} x ^ i \\ & = k (1 + x) ^ {k - 1} \end{align} $$

则答案为：

$$ \begin{align} & (n - 2)!\sum_{\sum a_{i} = n - 2} \prod_{i = 1} ^ {n} \frac{d_{i} ^ {\underline{a_{i} + 1}}}{a_{i}!} \\ = & (n - 2)![x ^ {n - 2}] \prod_{i = 1} ^ {n} F_{d_{i}}(x) \\ = & (n - 2)! \left(\prod_{i = 1} ^ {n} d_{i}\right) \left([x ^ {n - 2}]\prod_{i = 1} ^ {n} (1 + x) ^ {d_{i} - 1}\right) \\ = & (n - 2)! \left(\prod_{i = 1} ^ {n} d_{i}\right) \left([x ^ {n - 2}](1 + x) ^ {\sum (d_{i} - 1)}\right) \\ = & (n - 2)! \left(\prod_{i = 1} ^ {n} d_{i}\right) \binom{\sum (d_{i} - 1)}{n - 2} \\ = & \left(\prod_{i = 1} ^ {n} d_{i}\right) \left(\sum (d_{i} - 1)\right) ^ {\underline{n - 2}} \end{align} $$

直接计算即可。

时间复杂度：$\mathcal O(n)$。

Code

#include <bits/stdc++.h>
typedef long long int64;

const int MOD = 998244353;
int n;

int calc(int64 n, int m) {
    if (m > n) {
        return 0;
    }
    int ans = 1;
    for (int64 i = n; i >= n - m + 1; i--) {
        ans = (int64)ans * (i % MOD) % MOD;
    }
    return ans;
}
int main() {
    scanf("%d", &n);
    int ans = 1;
    int64 sum = 0;
    for (int x, i = 1; i <= n; i++) {
        scanf("%d", &x);
        ans = (int64)ans * x % MOD;
        sum += x - 1;
    }
    printf("%lld\n", (int64)ans * calc(sum, n - 2) % MOD);
    return 0;
}