Codeforces1009E (EDU47.E) Intercity Travellingzhao 找规律 数学期望

Codeforces1009E (EDU47.E) Intercity Travelling

题面:

  • 从数轴的0到n，中间的整数点都有可能有休息点也可能没有休息点。
  • 当你连续坐k站时，每两站间的疲劳值为a1,a2……ak。
  • 如果第k站有休息点，那么你可以在此处休息,然后接下来的站点的疲劳值又从a1开始，否则继续为ak+1。
  • 题目给你n和ai，每个站点有休息点的概率都是1/2，问你期望值 p*2^(n-1) 的值。

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
using namespace std;
#define rep(i,l,p) for(int i=l;i<=p;i++)
#define fread() freopen("in.txt","r",stdin)
#define sf scanf
#define pf printf
typedef long long ll;
int n,m;
const int MOD = 998244353;
ll a[1000005];
ll p[1000005];
int main(int argc, char const *argv[])
{sf("%d",&n);p[0] = 1;rep(i,1,n) p[i] = p[i-1]*2%MOD;rep(i,1,n) sf("%I64d",&a[i]);ll ans = a[n];rep(i,1,n-1){ans = (ans + (a[i] * (p[n-i] + p[n-i-1]*(n-i)%MOD)%MOD))%MOD;}pf("%I64d\n",ans);return 0;
}