http://codeforces.com/problemset/problem/1009/E   把n从2到5的情况都列出来会发现n每次加1 就只是在最高位加一个数字 n=2 即1 3 n=3 即1 3 8 n=5 即1 3 8 20 48 规律就是cs[k]=cs[k-1]*3-(k-2)的前缀和     #include<map>#include<stack>#incl

题目传送门：E. Intercity Travelling   题意：数轴上从0出发到n，值为1 - （n-1）的点中均可以休息，也可以不休息。现在给定一个数组a[ ]，a[i]表示走长度为i的距离的困难度（保证a[i+1]>a[i]），设每种情况出现的可能性均相同，求所有可能性的期望困难度之和p*2^(n-1)。   思路：有题意可知，总共有2^(n-1)种情况。分别统计所有情况中

Problem - 1009E - Intercity Travelling 题意： 从0走到n，休息后走的第 i km 的难度为 ai ，刚开始从 a1 开始每次经过休息点重新置一 休息点的个数和分布是随机的，并且概率相同 求从 0 到 n 的难度的期望   题解： 每个点是休息点和不是休息点的概率都为0.5 第 i km的难度概率分布为， P(Xi = a1) = 0.5 (

题意： 你需要从坐标0开车到坐标n，其中坐标1....n-1可以设置休息站。 当你连续开k站时，每两站间的疲劳值为a1,a2……ak，如果第k站有休息点，那么你可以在此处休息，然后接下来的站点的疲劳值又从a1开始，否则继续为ak+1 求所有休息站情况的疲劳值总和 思路： 也就是求和 sum(a[i] * 消耗a[i]出现的总次数) (i->1,2,3,…n); 我们可以按照这种思路，统

题目：戳这里 题意：从0走到n，难度分别为a1~an，可以在任何地方休息，每次休息难度将重置为a1开始。求总难度的数学期望。 解题思路： 跟这题很像，利用期望的可加性，我们分析每个位置的状态，不管怎么休息位置1的难度永远是a1，因此其期望为a1*2^(n-1)，其他点出现a1的话，说明上一个点绝对休息过，剩下的都与其无关，也就是2^(n-2)，所有的统计起来，则a1的出现次数为2^(n-1)+(

数学题(期望+概率)CodeForces 1009E-Intercity Travelling 题目链接：E. Intercity Travelling 思路： 路程为n,给定困难度（a1~an），过程中(1~n-1)都可能有休息站，概率为1/2，如果第k点有休息站，那么下一站困难度从a1开始，否则困难度加一，求到终点困难度的期望值*2^(n-1) 推算规律 竖着看，对路

题目传送：http://codeforces.com/problemset/problem/1009/E 题目大意       给你一个长度为n的序列a，a[i]代表连续走第 i km时，第 i km的花费。现有一段长度为n km的路，输出从头走到尾的花费的期望*2n-1(一定是个整数)对998244353取模后的结果。 输入格式       第一行一个整数 n ，意义如题目大意所述。

题目 题意： 司机不休息的话，走1公里，消耗a1,再走一公里消耗a2，然后a3、a4。这样消耗下去。 有休息站，可以让a数组重新数。 问你总消耗的期望*2^(n-1)。   POINT： 可以推一下。px为x这个坐标的期望组成。 p1=1*a1 （第一个永远是a1） p2=1/2*a1+1/2*a2 (2这个点，有1/2的概率有休息站，那么1/2*a1，有1/2没有，那么从