E. Intercity Travelling

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--E. Intercity Travelling

题解

高档题。题意大概是某人从x=0旅行至x=n,在上次休息过后走当前公里的疲劳值为ai,休息点的位置不确定,求疲劳值之和的数学期望。
对于某个位置x=i,疲劳值为ai的可能休息点情况数为2^(n-i)种,疲劳值为aj(j<i)的可能休息点情况数为2^(n-i-1)种。处理过后发现对于某个疲劳值ai,其总的出现情况数为2^(n-i)+2^(n-i-1)*(n-i)。之后直接套公式即可。

代码

#include <iostream>
using namespace std;
const long long mod = 998244353;
long long n;
long long a[1000005];
long long b[1000005];
long long ans(0);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    b[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        b[i] = (b[i - 1] << 1) % mod;
    }
    for (int i = 1; i <= n; i++) {
        ans += a[i] * b[n - i] % mod;
        ans += a[i] * b[n - i - 1] % mod * (n - i) % mod;
    }
    cout << ans % mod;
}

标签: math, combinatorics, probabilities

添加新评论