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