首页 > 其他 > 详细

Intercity Travelling CodeForces - 1009E (组合计数)

时间:2019-07-14 20:22:00      阅读:111      评论:0      收藏:0      [点我收藏+]

大意: 有一段$n$千米的路, 每一次走$1$千米, 每走完一次可以休息一次, 每连续走$x$次, 消耗$a[1]+...+a[x]$的能量. 休息随机, 求消耗能量的期望$\times 2^{n-1}$.

 

简单计数题, 枚举每种长度的贡献.

#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
const int P = 998244353, INF = 0x3f3f3f3f;

const int N = 1e6+10;
int n,a[N],po2[N];

int main() {
	scanf("%d", &n);
	REP(i,1,n) scanf("%d", a+i),(a[i]+=a[i-1])%=P;
	if (n==1) return printf("%d\n",a[n]),0;
	if (n==2) return printf("%d\n",2*a[1]+a[2]),0;
	po2[0] = 1;
	REP(i,1,n) po2[i] = po2[i-1]*2ll%P;
	int ans = a[n];
	REP(i,1,n-1) ans = (ans+((n-i-1ll)*po2[n-i-2]%P+2ll*po2[n-i-1])*a[i])%P;
	printf("%d\n", ans);
}

 

Intercity Travelling CodeForces - 1009E (组合计数)

原文:https://www.cnblogs.com/uid001/p/11185436.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!