题目大意：
有(n)的点，每个点有一个权值(d_i)，表示这个点上有多少个孔。你可以连接(n-1)条边，每条边可以连接分别属于两个点的两个孔。一个孔不能连两条边。要求最后这样使这(n)个联通，即找到完全图的一个生成树。
前置知识
来自于prufer序列的一个结论：在完全图中，如果(n)个点的度数分别为(D_1,D_2,cdots,D_n)，那么满足这种条件的生成树个数是
[frac{(n-2)!}{prodlimits_{k=1}^n(D_k-1)!}
]
吸收/提取恒等式：
[inom{n}{m}=frac{n}{m}inom{n-1}{m-1}
]
题解
考虑在最后的一种生成树中，(n)个点的度数分别为(D_1,D_2,cdots,D_n)。因为每个点在选择要连接的孔时是有序的，则这种方案的贡献是：
[frac{(n-2)!}{prodlimits_{k=1}^n(D_k-1)!}prod_{k=1}^ninom{d_k}{D_k}D_k!
]
注意到(sumlimits_{k=1}^nD_k=2(n-1))，所以事实上，我们可以构造出一个卷积来求答案(S)。
[Ans=(n-2)![x^{2n-2}]prod_{k=1}^nF_k(x)
]
[egin{align*}
F_t(x)&=sum_{k=0}^inftyinom{d_t}{k}frac{k!}{(k-1)!}x^k\
&=sum_{k=0}^inftyinom{d_t}{k}k x^k\
&=sum_{k=1}^inftyinom{d_t-1}{k-1}d_tx^k\
&=d_tsum_{k=0}^inftyinom{d_t-1}{k}x^{k+1}\
&=d_txsum_{k=0}^inftyinom{d_t-1}{k}x^k\
&=d_tx(1+x)^{d_t-1}
end{align*}
]
记(S)为所有(d)的和，(T)为所有(d)的积，我们有：
[egin{align*}
Ans&=(n-2)![x^{2n-2}]prod_{k=1}^nd_kx(1+x)^{d_k-1}\
&=(n-2)![x^{2n-2}]Tx^n(1+x)^{S-n}\
&=(n-2)!T[x^{n-2}](1+x)^{S-n}\
&=(n-2)!Tinom{S-n}{n-2}\
&=T(S-n)^underline{n-2}
\
end{align*}
]
问题解决。时间复杂度(O(n))
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
int n;
ll sn,ans=1;
inline ll add(ll a,ll b){return a+b>=mod?a+b-mod:a+b;}
inline ll mul(ll a,ll b){return a*b%mod;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
sn=add(sn,x);
ans=mul(ans,x);
}
for(int i=0;i<n-2;i++)ans=mul(ans,sn-n-i);
printf("%lld
",ans);
}