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

本是古典何须时尚 2022-05-17 11:57 201阅读 0赞

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

--------------------

*  ## 题目链接：[E. Intercity Travelling][] ##
 *  ## 思路： ##

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

推算规律

![70][]

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

![70 1][]

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

![70 2][]

再乘 2^(n-1)

![70 3][]

这就是最后的公式啦 ，题目要求取模，取模也是艺术呀~输入用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;
    
    }

困~

[E. Intercity Travelling]: http://codeforces.com/problemset/problem/1009/E
[70]: /images/20220517/dd13f1564a494791af0f2f91d1b05565.png
[70 1]: /images/20220517/e323fca453ce44389da245ce4145b043.png
[70 2]: /images/20220517/3ff7f29881694995babc531ce24cb51e.png
[70 3]: /images/20220517/5b34c36826a746f497bb9673ba446d74.png