Beyond awesome | 越而胜己

We want to use linearity of expectation to calculate the expectation of the total difficulty $E[X] = \sum E[X_i]$. Note that
$$E[X_i] = \sum_{j=1} ^{i} P(X_i = a_j) a_j = \frac{a_1}{2} + \frac{a_2}{4} + \cdots + \frac{a_{i-1}}{2 ^{i-1}} + \frac{a_{i}}{2 ^{i-1}}$$
(yes, the last two terms have the same denominator). Then we calculate $\sum E[X_i]$, which is $\sum_{i=1} ^{n} \frac{1}{2 ^i} (n-i+2) a_i$.

#include <iostream>
#include <cstdio>
#include <cinttypes>

#define MODULUS (998244353)

using namespace std;

uint64_t a[1000001];

int main(int argc, char *argv[]) {
uint64_t n;
scanf("%" SCNu64, &n);
for (uint64_t i = 1; i <= n; i++) {
scanf("%" SCNu64, &a[i]);
}
uint64_t pow_of_two = 1;
uint64_t sum = a[n];
for (uint64_t k = n - 1; k >= 1; k--) {
uint64_t item = (n - k + 2) * a[k];
item %= MODULUS;
item *= pow_of_two;
item %= MODULUS;
sum += item;
sum = sum % MODULUS;
pow_of_two = pow_of_two * 2 % MODULUS;
}
cout << sum % MODULUS << endl;
return 0;
}

You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.