越而胜己 / 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;
}