数学题(期望+概率+快速幂)CodeForces 1009E-Intercity Travelling

• 数学题(期望+概率)CodeForces 1009E-Intercity Travelling

• 题目链接：E. Intercity Travelling

• 思路：

路程为n,给定困难度（a1~an），过程中(1~n-1)都可能有休息站，概率为1/2，如果第k点有休息站，那么下一站困难度从a1开始，否则困难度加一，求到终点困难度的期望值*2^(n-1)

推算规律

竖着看，对路径上每一点i，期望E为：

对每一横行看，会发现除了开头和后面的概率不一样，后面的概率是一样的，系数也一样，所以总期望为：

再乘 2^(n-1)

这就是最后的公式啦 ，题目要求取模，取模也是艺术呀~输入用cin会WA~

• 代码：

#include<iostream>
#include<cstdio>
using namespace std;#define MAX_SIZE 1000005
#define Mod 998244353 long long a[MAX_SIZE];
long long p = 0;
long long Pow = 1;
long long n;int main()
{cin >> n;for (long long i = 1; i <= n; i++)//cin >> a[i];scanf("%lld", &a[i]);p += a[n];for (long long i = n-1; i >= 1; i--){p += 2 * Pow*a[i] % Mod + (n - i)*Pow% Mod*a[i];p %= Mod;Pow = Pow * 2 % Mod;}cout << p << endl;return 0;}

困~