[数学记录]ARC106F Figures
command_block
2021-10-26 11:33:47
**题意** ： 有 $n$ 个元件和 $n-1$ 条导线，你需要用导线将元件联通。
第 $i$ 个元件有 $d_i$ 个不同的接口，导线可以接在接口上，同一个接口至多接一条导线。
两种方案不同当且仅当存在一对接口，在一种方案中有导线连接，而另一种方案中无导线连接。
答案对 $998244353$ 取模。
$n\leq 2\times 10^5$ ，时限$\texttt{2s}$。
------------
不难将题意转化为，已有 $n$ 个大小分别为 $a_i$ 的有标号树，加 $n-1$ 条边将其连成大树，且每个点度数最多额外增加一的方案数。
为了方便，改记：已有 $m$ 个总大小为 $n$ 的联通块，大小分别为 $a_{1\sim m}$ 。
将联通块视作大点。考虑一种可能的大点的度数序列 $d$ ，则对应连边方案数是 $\prod\limits_{i=1}^ma_i^{\underline d_i}$ 。
构造 `prufer` 序列 $p$ ，设 $c_i$ 为 $i$ 号大点的出现次数,有 $d_i=c_i+1$。
可写出：
$$
\begin{aligned}
{\rm Ans}&=\sum\limits_{p}\prod\limits_{i=1}^ma_i^{\underline{c_i+1}}\\
&=\prod\limits_{i=1}^ma_i\sum\limits_{p}\prod\limits_{i=1}^m(a_i-1)^{\underline{c_i}}\\
\end{aligned}
$$
注意到 $p$ 是全体 $m^{m-2}$ 个 $\{1\sim m\}^{m-2}$ 的序列，根据下降幂的二（多）项式定理有 $(\sum_{i=1}^{m-2}a_i-1)^{\underline{m-2}}=\sum\limits_{p\in\{1\sim m\}^{m-2}}\prod\limits_{i=1}^m(a_i-1)^{\underline {\sum_{j=1}^{m-2}[p_j=i]}}$ 。
于是：
$$
{\rm Ans}=\prod\limits_{i=1}^ma_i\Bigg(\sum_{i=1}^{m-2}a_i-1\Bigg)^{\underline{m-2}}
$$
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
const int mod=998244353;
int m,n;
int main()
{
scanf("%d",&m);
int ans=1;
for (int i=1,x;i<=m;i++){
scanf("%d",&x);
ans=1ll*ans*x%mod;
n=(n+x-1)%mod;
}
for (int i=0;i<m-2;i++)ans=1ll*ans*(n-i)%mod;
printf("%lld",ans);
return 0;
}
```