[atAGC106F]Figures

考虑purfer序列，若生成树的pufer序列为$p_{i}$，则答案为$(prod_{i=1}^{n}a_{i})sum_{p}prod_{i=1}^{n}frac{(a_{i}-1)!}{(a_{i}-1-s_{i})!}$（其中$s_{i}$为$p$中点$i$出现的次数，即度数减1）

（以下令$a_{i}$减1）观察到式子只与$s_{i}$有关，对于相同的$s_{i}$对应$p_{i}$有$frac{(n-2)!}{prod_{i=1}^{n}s_{i}!}$种，令$C=(n-2)!prod_{i=1}^{n}a_{i}$，代入即$ans=Csum_{sum_{i=1}^{n}s_{i}=n-2}prod_{i=1}^{n}frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!}$

令$f(x)=sum_{k=0}^{n-2}(sum_{sum_{i=1}^{n}s_{i}=k}frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!})x^{k}=sum_{s_{i}}prod_{i=1}^{n}frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!}cdot x^{s_{i}}$，答案即$f(x)[x^{n-2}]$

不妨先枚举$s_{1},s_{2},..$，再提取出对应位置上的式子作为公因式，之后由于各位上完全独立，再将结果乘起来就是原式，即$f(x)=prod_{i=1}^{n}sum_{s_{i}=0}^{a_{i}}frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!}cdot x^{s_{i}}=(1+x)^{sum_{i=1}^{n}a_{i}}$

因此$f(x)[x^{n-2}]=c(sum_{i=1}^{n}a_{i},n-2)$（注意这里的$a_{i}$减了1），发现$(n-2)!$已经被抵消掉，因此直接枚举$sum_{i=1}^{n}a_{i}$到$sum_{i=1}^{n}a_{i}-(n-2)+1$即可

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
int n,x,s,ans;
int main(){
    scanf("%d",&n);
    ans=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        ans=1LL*ans*x%mod;
        s=(s+x-1)%mod;
    }
    for(int i=0;i<n-2;i++)ans=1LL*ans*(s-i+mod)%mod;
    printf("%d",ans);
}