题目：戳这里

题意：从0走到n，难度分别为a1~an，可以在任何地方休息，每次休息难度将重置为a1开始。求总难度的数学期望。

解题思路：

跟这题很像，利用期望的可加性，我们分析每个位置的状态，不管怎么休息位置1的难度永远是a1，因此其期望为a1*2^(n-1)，其他点出现a1的话，说明上一个点绝对休息过，剩下的都与其无关，也就是2^(n-2)，所有的统计起来，则a1的出现次数为2^(n-1)+(n-1)*2^(n-2)。同理求a2,a2绝对不会出现在位置1，而出现在位置2时，只会影响位置1，出现在其他点，会影响其前两个点，则a2的出现次数为2^(n-2)+(n-2)*2^(n-3)，再推推a3,a4，基本可以推出这个公式E[i]=(2^(n-i)+(n-i)*2^(n-i-1))*a[i]。

注意这题卡时间，不要用快速幂。

附本人代码：

1 #include
2 typedef long long ll;
3 const int maxn = 1e6+10;
4 const ll inf = 1e18;
5 const ll mod = 998244353;
6 using namespace std;
7 ll qmul(ll a, ll b) {
8 ll res = 0;
9 while(b) {
10 if(b&1) res = (res + a) % mod;
11 b>>=1;
12 a = (a + a) % mod;
13 }
14 return res;
15 }
16 ll qmod(ll a, ll b) {
17 ll res = 1;
18 while(b) {
19 if(b&1) res = qmul(res, a) % mod;
20 b>>=1;
21 a = qmul(a,a)%mod;
22 }
23 return res;
24 }
25 ll rec[maxn];
26 ll nu[maxn];
27 int main(){
28 ll n, m;
29 scanf("%lld", &n);
30 rec[0]=1ll;
31 for(ll i = 1; i <= n; ++i) {
32 rec[i] = qmul(2ll, rec[i-1]);
33 }
34 for(ll i = 1; i <= n; ++i) {
35 scanf("%lld", nu+i);
36 }
37 ll ans = 0;
38 for(ll i = 1; i <= n; ++i) {
39 ans = (ans + qmul(nu[i], rec[n-i] + qmul(n-i, rec[n-i-1ll]))) %mod;
40 }
41 printf("%lld\n", ans);
42 return 0;
43 }