Codeforces 1009 E Intercity Travelling 思维+期望

思维+期望"/>

Codeforces 1009 E Intercity Travelling 思维+期望

按官方题解的说法，第i公里的难度，是diffi=a12+a222+⋯+ai−12i−1+ai2i−1diffi=a12+a222+⋯+ai−12i−1+ai2i−1。 这么一来，我们可以得到这样的关系： diff1=a1diff1=a1, diffi+1=diffi−ai2i+ai+12i。真棒棒！这样我们就可以顺利的写出这道题了！

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;int n;
const long long mod=998244353;
long long a[1000005],tmp[1000005],diff[1000005];int main()
{scanf("%d",&n);for (int i=1; i<=n; i++){scanf("%lld",&a[i]);}tmp[0]=1;tmp[1]=2;for (int i=2; i<=n; i++){tmp[i]=(tmp[i-1]*2)%mod;}diff[1]=(a[1]*tmp[n-1])%mod;for (int i=2; i<=n; i++){diff[i]=(diff[i-1]-(a[i-1]*tmp[n-i])%mod+(a[i]*tmp[n-i])%mod+mod)%mod;}long long ans=0;for (int i=1; i<=n; i++){ans=(ans+diff[i])%mod;}cout<<ans<<endl;return 0;
}