Codefroces - 1009E - Intercity Travelling （概率期望）

本文主要是介绍Codefroces - 1009E - Intercity Travelling （概率期望），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem - 1009E - Intercity Travelling

题意：

从0走到n，休息后走的第 i km 的难度为 ai ，刚开始从 a1 开始每次经过休息点重新置一

休息点的个数和分布是随机的，并且概率相同

求从 0 到 n 的难度的期望

题解：

每个点是休息点和不是休息点的概率都为0.5

第 i km的难度概率分布为，

P(Xi = a1) = 0.5 (i > 1) P(Xi = a1) = 1 (i = 1) 因为第一个位置只可能为a1，后面的只有第i-1个位置为休息点该点才可能是a1

P(Xi = a2) = (0.5)^2 (i > 2) P(Xi = a2) = 0.5 (i = 2) P(Xi = a2) = 0 (i < 2) 为a2 就必须要i-1不是且i-2是

然后以此类推

就可以得到第 i km的难度期望 $EXi = \sum_{j=1}^{i}P(Xi = aj) aj=\frac{a1}{2^1}+\frac{a2}{2^2}+...++\frac{aj}{2^{j-1}}$

然后可以得到整体的期望 $p=\sum EXi = \sum_{i=1}^{n}(\frac{ai}{2^{i-1}}+(n-i)\frac{ai}{2^i})$

$p * 2^{n-1} = \sum_{i=1}^{n}(2^{n-i}ai + (n-i)2^{n-i-1}ai)$

就可以直接求了

可以从后面推，这样可以直接得到2^n-i

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
typedef long long int LL;
const int maxn = 1e6 + 10;
const int mod = 998244353;
LL n,a[maxn];
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);LL ans = a[n], pow2 = 1;for(int i=n-1;i>=1;i--){ans += pow2 * 2 * a[i] % mod + (n-i) * pow2 % mod * a[i];ans %= mod;pow2 = pow2 * 2 % mod;}printf("%lld\n", ans);return 0;
}

这篇关于Codefroces - 1009E - Intercity Travelling （概率期望）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！