Codeforces 1009 E. Intercity Travelling（计数）

1009 E. Intercity Travelling



题意：一段路n个点，走i千米有对应的a[i]疲劳值。但是可以选择在除终点外的其余n-1个点休息，则下一个点开始，疲劳值从a[1]开始累加。休息与不休息等概率，设疲劳值总和的期望为p,求p*2

思路：由于期望乘上了2，所以数学意义就是求所有休息情况下的疲劳值总和。问题转化为，每种疲劳出现的次数Ni。网上题解大多数从组合数的角度计数，可能是我理解能力不够，总觉得讲的不太严谨，推导的过程略显随意，更多像是找规律的结果。琢磨了一会，觉得这样计数更容易理解：


对于疲劳a[1]而言，一个点就能出现。由于第一个点一定是a[1]，则第一个点的a[1]的出现次数就是2（后面的n-1个点任取，任取是指从a[1]开始还是接前一个的疲劳，2种情况）。而对于其余的任意一个点，出现a[1]的情况共2种（第一个点固定是a[1],还剩n-2个点任取），这样的点有n-1个。故N1 = 2+（n-1) * 2.


对于疲劳a[2]而言，一次要选连续的两个点才能出现。如果选了1，2两点，那么剩下n-2个点任取，共2。而且对于其余的任意连续两点，第一个点是不会变的，除去本身两个确定，还剩n-3个点任取，共2种情况，这样的连续两点有n-2种。因此N2 = 2 + (n-2) * 2.


写到2就能推广到i：a[i]只能出现在连续的i个点下。于是分开讨论选连续的i个点里是否包含1，包含的话，共2种情况，不包含则有2种情况，这样的选法有n-i种。Ni = 2 + (n-i) * 2.


答案就是∑(Ni * ai)。



代码：

#include<bits/stdc++.h>

#define dd(x) cout<<#x<<" = "<<x<<" "

#define de(x) cout<<#x<<" = "<<x<<"\n"

#define sz(x) int(x.size())

#define All(x) x.begin(),x.end()

#define pb push_back

#define mp make_pair

#define fi first

#define se second

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> P;

typedef priority_queue<int> BQ;

typedef priority_queue<int,vector<int>,greater<int> > SQ;

const int maxn=1e6+10,mod=998244353,INF=0x3f3f3f3f;

ll a[maxn],pw[maxn];

void init()

{

	pw[0]=1;

	for (int i=1;i<maxn;++i)

		pw[i]=pw[i-1]*2%mod;

}

inline ll add(ll a,ll b)

{

	a+=b;

	return a>=mod?a-mod:a;

}

int main()

{

	ll n;

	cin>>n;

	init();

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

		scanf("%lld",&a[i]);

	ll ans=0;

	for (ll i=1;i<=n;++i)

		ans=add(ans,add(pw[n-i],(n-i+mod)%mod*pw[n-i-1]%mod)*a[i]%mod);

	cout<<ans;

	return 0;

}