题解 | #连通块计数#

链接：https://ac.nowcoder.com/acm/problem/19800 来源：牛客网

题目描述

小 A 有一棵长的很奇怪的树，他由 n 条链和 1 个点作为根构成，第 i 条链有 ai 个点，每一条链的一端都与根结点相连。 现在小 A 想知道，这棵长得奇怪的树有多少非空的连通子树，你只需要输出答案对 998244353 取模的值即可

输入描述:

第一行一个正整数 n

第二行 n 个正整数 a1…an

输出描述:

输出答案对 998244353 取模后的值

示例1

输入

2

1 1

输出

6

备注:

$1\le n\le 10^{5}1\; \backslash leq\; n\; \backslash leq\; 10^5$

$1\le a_i\le 10^{7}1\; \backslash leq\; a\_i\; \backslash leq\; 10^7$

题解

遇到这种计数类题目， 最重要的就是做到不重不漏， 首先要是想着暴力的做法是肯定会超时的， 那接下来我们就要思考一些可以做到不重不漏的分类方法，结合题目我们可知，此题的树是有一个根节点，和其他若干个链组成的，若其中的一条链想要和其他的链相连，就必须要经过根节点。通过这样的分析我们可以将连通块的计数分为两种情况，分别为

1. 不通过根节点与其他链相连

这种情况我们每一条链分别进行计数，算上总和就是这种情况连通块的总数。

2. 通过根节点与其他链相连

这种情况我们可以考虑到排列组合，假设到第$i$条链时， 链上的结点为$a_i$个， 那么这条链与根节点相连的情况
就有$a_i + 1$种情况(包含0个点与根节点相连的情况),所以在每次添加新链的时候，结果都要×(n + 1)
最后将这两种情况计数的数量相加便是答案

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const int mod = 998244353;
int main()
{
    i64 n;
    cin>>n;
    i64 ans = 1;
    i64 sum = 0;
    for(int i = 0;i < n;i ++)
    {
        int a;
        cin>>a;
        ans = 1LL * ans * (a + 1) % mod;
        sum += 1LL * a * (a + 1) / 2 % mod;
    }
    
    cout << (ans + sum ) % mod <<endl;
    return 0;
}