題目連結：傳送門
題目大意：Leha從數軸的0到n，中間的整數點都有可能有休息點也可能沒有休息點。當你連續坐k站時，每兩站間的疲勞值為a1,a2……ak，如果第k站有休息點，那麼你可以在此處休息，然後接下來的站點的疲勞值又從a1開始，否則繼續為ak+1。題目給你n和ai，每個站點有休息點的機率都是1/2，問你期望值*2^(n-1)的值。
思路：我們知道從0到1的疲勞值一定為a1，1到2的疲勞值為a1(1/2),a2(1/2)，括号裡面為機率，當1有休息點時為a1，否則為a2；2到3的疲勞值為a1(1/2),a2(1/4),a3(1/4)……以此類推得到下圖：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 1e6 + 7;
int n;
ll ans;
ll a[maxn], p[maxn];
int main() {
scanf("%d", &n);
p[0] = 1;
for(int i = 1; i <= n; i++) {
p[i] = p[i-1] * 2 % mod;
}
for(int i = 1; i <= n; i++) {
scanf("%I64d", &a[i]);
}
ans = a[n];
for(int i = 1; i < n; i++) {
ans = (ans + (a[i] * (p[n - i] + p[n - i - 1] * (n - i) % mod) % mod) % mod) % mod;
}
printf("%I64d\n", ans);
return 0;
}