连通块计数
描述
题目描述：
小 A 有一棵长的很奇怪的树，他由 n 条链和 1 个点作为根构成，第 i条链有 ai 个点，每一条链的一端都与根结点相连。
现在小 A 想知道，这棵长得奇怪的树有多少非空的连通子树，你只需要输出答案对 998244353 取模的值即可
输入：
第一行一个正整数 n
第二行 n 个正整数 a1…an
1≤n≤10^5
1≤ai≤10^7
输出：
输出答案对998244353 取模后的值
样例输入
2
1 1
样例输出
6
包含中心的联通块数量 ∏(ai+1)--(1<=i<=n)
不包含中心的联通块数量∑(ai(ai+1)/2)--(1<=i<=n),也就是C(ai+1,2)，每条链选择2条边截断
#include <cstdio>
#include <cstring>
#include <cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mo=;
const int maxn=1e7+;
int n;
ll a[],ans=;
ll fun[maxn];
ll kpow(ll a,ll b)
{
ll res=;
while(b>)
{
if(b&) res=res*a%mo,b--;
a=a*a%mo;
b/=;
}
return res%mo;
}
ll C(ll n,ll m)
{
if(n<m) return ;
return fun[n]*kpow(fun[m]*fun[n-m]%mo,mo-)%mo;
}
void init(){
fun[]=;
for(int i=;i<=maxn;i++)
fun[i]=fun[i-]*i%mo;
}
int main()
{
init();
cin>>n;
for(int i=;i<n;i++){
cin>>a[i];
ans+=C(a[i]+,);
ans%=mo;
}
ll b=;
for(int i=;i<n;i++){
b*=(a[i]+);
b%=mo;
}
cout<<(ans+b)%mo<<endl;
return ;
}