本文共 1182 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

        小 A 有一棵长的很奇怪的树，他由 n 条链和 1 个点作为根构成，第 i 条链有 ai 个点，每一条链的一端都与根结点相连。

现在小 A 想知道，这棵长得奇怪的树有多少非空的连通子树，你只需要输出答案对 998244353 取模的值即可

题解：

      注意题目说的是每条链的一端都与根节点相连，只是这条链的最末端，端点与根节点相连，那些在这条链上却非末端端点的点不与根节点相连

就像这个样子

这样的话，连通子树的个数要分两种情况

1.包含根节点

       对于每一条链，链的末端与根节点相连，构成了一个回路，每一条链有a[i]个点，那么就有在这条链选0个、选1个、选2个...选a[i]个，共a[i]+1种情况， 

要构成连通子树，必须得是相连的，就是根-1，根-1-2，根-1-2-3......这样的情况，不可能直接选中途的1-2这样

2.不包含根节点

       对于每一条链，有a[i]个节点，那么这条链能形成的子树个数是 ,这是通过挨个数找出的规律，

例如本图最左边的链，分别给点标号为1,2,3,4

子树的个数为

①4个节点分别是1个

②1-2，1-2-3，1-2-3-4

③2-3,2-3-4,

④3-4

共10个

因为没跟根节点连接，就不能乘了，要加起来，所以 

 

踩的坑：

      首先，这个题有除以2，但是不用求逆元，当能够保证整除的情况下不需要求逆元（a[i]*(a[i]+1)也一定能够整除2），当是分数的情况下才需要求逆元(又涨姿势了)，但是求了也没错。

     其次，在算的过程中，ans是long long 类型的，而a[i]是int型的，算的过程有相乘，数大了就会爆int的，没有转换类型，导致WA了一发。。。。

#include
   
    using namespace std;#define mod 998244353typedef long long ll;int a[100010];int main(){//   freopen("input.txt","r",stdin);    int n;    scanf("%d",&n);    for(int i=1; i<=n; ++i)        scanf("%d",&a[i]);    ll ans1=1;    for(int i=1; i<=n; ++i)    {        ans1*=a[i]+1;        ans1%=mod;    }    ll ans2=0;    for(int i=1; i<=n; ++i)    {        ans2+=(ll)(a[i])*(a[i]+1)/2%mod;        ans2%=mod;    }    printf("%lld\n",(ans1+ans2)%mod);    return 0;}