牛客国庆集训派对Day4 I-连通块计数（思维，组合数学）

时间：2021-05-30 14:59:41

链接：https://www.nowcoder.com/acm/contest/204/I

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 1048576K，其他语言2097152K

64bit IO Format: %lld

题目描述

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

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

输入描述:

第一行一个正整数 n

第二行 n 个正整数 a1…an

输出描述:

输出答案对 998244353 取模后的值

示例1

输入

2

1 1

输出

6

备注:

1≤ n≤ 10^5

1≤ ai≤ 10^7

思路

连通块分成两种：连通子树的点在同一条链上和在多条链上；

  • 连通子树的点在一条链上：算上根节点，每条链上一共有a[i]+1个点，每条链上有牛客国庆集训派对Day4 I-连通块计数（思维，组合数学）个连通子树，所以该情况的连通子树共有牛客国庆集训派对Day4 I-连通块计数（思维，组合数学）个
  • 连通子树的点在多条链上：每条链上有选择0,1,2,......a[i]这a[i]+1种选法，所以该情况一共有牛客国庆集训派对Day4 I-连通块计数（思维，组合数学）个连通子树

然后把上述两种情况的连通子树数量相加即可

AC代码

/*

* @Author: WZY

* @Date:   2018-10-09 16:36:48

* @Last Modified by:   WZY

* @Last Modified time: 2018-10-09 17:28:52

*/

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#include <time.h>

#define ll long long

#define ull unsigned long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

#define lson o<<1

#define rson o<<1|1

#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"

const double E=exp(1);

const int maxn=1e6+10;

const int mod=998244353;

using namespace std;

ll a[maxn];

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	#ifndef ONLINE_JUDGE

	    freopen("in.txt", "r", stdin);

	    freopen("out.txt", "w", stdout);

	    double _begin_time = clock();

	#endif

	ll n;

	cin>>n;

	ll res=0;

	for(int i=0;i<n;i++)

	{

		cin>>a[i];

		res=res+(a[i]+1)*a[i]/2%mod;

	}

	ll ans=1;

	for(int i=0;i<n;i++)

		ans=ans*(a[i]+1)%mod;

	cout<<(ans+res)%mod<<endl;

	#ifndef ONLINE_JUDGE

	    long _end_time = clock();

	    printf("time = %lf ms.", _end_time - _begin_time);

	#endif

	return 0;

}

相关文章