cf1009 E. Intercity Travelling

题意：

从0走到n，每一步向右走1，走第 \(i\) 步的代价为 \(a_i\)。可以任意整点休息任意次，每次休息后步数清零。求总代价的数学期望与 \(2^{n-1}\) 的乘积。

\(n\le 1e6\)

思路：

pow2[0] = 1;
for(int i = 1; i < N; i++) pow2[i] = pow2[i-1] * 2 % mod;

cin >> n;
for(int i = 1; i <= n; i++) {
    ll x; cin >> x;
    x *= (pow2[n-i] + (n-i) * pow2[n-i-1] % mod) % mod;
    (ans += x % mod) %= mod;
}
cout << ans;