問題 I: 連通塊計數

時間限制: 1 Sec??內存限制: 128 MB
提交: 108??解決: 45
[提交] [狀態] [討論版] [命題人:admin]

題目描述

小A有一棵長的很奇怪的樹，他由n條鏈和1個點作為根構成，第i條鏈有ai個點，每一條鏈的一端都與根結點相連。
現在小A想知道，這棵長得奇怪的樹有多少非空的連通子樹，你只需要輸出答案對998244353取模的值即可

?

輸入

第一行一個正整數n
第二行n個正整數a1…an
1≤n≤105
1≤ai≤107

?

輸出

輸出答案對998244353取模后的值

?

樣例輸入

2
1 1

?

樣例輸出

6

AC代碼：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <limits.h>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#define ll long long 
#define inf 0x3f3f3f3f
using namespace std;
const int man=1e5+50;
const ll mod=998244353;
ll a[man],b[man];
ll n,i,j;
int main() 
{#ifndef ONLINE_JUDGE// freopen("in.txt","r",stdin);#endifscanf("%lld",&n);for(i=0;i<n;i++)scanf("%lld",&a[i]);ll m=1;for(i=0;i<n;i++)m=(m*(a[i]+1))%mod;for(i=0;i<n;i++)m=(m+a[i]*(1+a[i])/2%mod)%mod;printf("%lld\n",m);return 0;
}

?