原题地址
大致题意:有n个关卡，若干个存档点，闯关成功就进入下一关，否则回到之前最近的存档点。成功的概率为 1 2 \frac{1}{2} 21,现在给你走的步数的期望，要求构造一图满足这个期望。
题解：
显然各个存档点之间的期望是独立的，可以直接相加。只需要考虑一个存档点下有n个关卡通关所需的期望。
那么就等价于下面这个子问题。
子问题：抛硬币，如果连续n次正面则游戏结束，否则就一直抛,求抛的次数的期望。
考虑：如果抛到反面就相当于回到了起点，如下图：
设E(n)为该子问题的解，那么考虑递推式：
对于E(n-1)有 1 2 \frac{1}{2} 21的概率抛到正面从而变到E(n)，还有 1 2 \frac{1}{2} 21的概率回到原点那么再走到第n个点的概率就是E(n):
E ( n ) = 1 2 ( E ( n − 1 ) + 1 ) + 1 2 ( E ( n − 1 ) + 1 + E ( n ) ) E(n)=\frac{1}{2}(E(n-1)+1)+\frac{1}{2}(E(n-1)+1+E(n)) E(n)=21(E(n−1)+1)+21(E(n−1)+1+E(n))
解得：
E ( n ) = 2 ∗ E ( n − 1 ) + 2 E(n)=2*E(n-1)+2 E(n)=2∗E(n−1)+2
用上面的思维考虑递推起点E(1):
E ( 1 ) = 1 2 + 1 2 ( 1 + E ( 1 ) ) E(1)=\frac{1}{2}+\frac{1}{2}(1+E(1)) E(1)=21+21(1+E(1))
解得:E(1)=2;
由递推式可得：
E ( n ) + 2 = 2 ∗ ( E ( n − 1 ) + 2 ) E(n)+2=2*(E(n-1)+2) E(n)+2=2∗(E(n−1)+2)
E ( n ) = 2 n + 1 − 2 E(n)= 2^{n+1}-2 E(n)=2n+1−2
解决该子问题后原问题可以得到轻松解决。
相似的题目：：https://codeforces.com/gym/102881/problem/L
子问题扩展：抛一枚硬币，抛到正面的概率是 1 x \frac{1}{x} x1,如果抛到正面则游戏结束，否则就一直抛，求抛的次数的平方的期望，即如果抛的次数是m，则求E( m 2 m^2 m2).
考虑抛k次抛到正面的概率：
前(k-1)次抛的一定都是反面，而第k次恰好是正面，那么其概率为:
( 1 − 1 x ) k − 1 ∗ 1 x (1-\frac{1}{x})^{k-1}*\frac{1}{x} (1−x1)k−1∗x1
那么可以得到
E ( m 2 ) = lim n → ∞ ∑ i = 1 n i 2 ∗ ( 1 − 1 x ) i − 1 ∗ 1 x E(m^2)=\lim_{n\rightarrow\infty}\sum_{i=1}^{n}i^2*(1-\frac{1}{x})^{i-1}*\frac{1}{x} E(m2)=n→∞limi=1∑ni2∗(1−x1)i−1∗x1
由于 1 x \frac{1}{x} x1是常数可以提到求和符号的外面，那么剩下的可以通过两次
错位相减(百度百科)得到答案,化简完了之后取n为无穷，则可以得到答案。
化简得：
E ( m 2 ) = 2 ∗ x 2 − x E(m^2)=2*x^2-x E(m2)=2∗x2−x
相似的题目：https://codeforces.com/gym/102861/problem/A
子问题扩展：每次从[A,B]内取一个整数，使得取的所有数的加和恰好等于n，求所取次数的期望E(n)。
显然E(n)可以由B-A+1种状态转移而来，而且由这些状态转移而来是等概率的。设L=B-A+1有:
E ( n ) = E ( n − A ) L + E ( n − A − 1 ) L + . . . . . . + E ( n − B ) L + 1 E(n)=\frac{E(n-A)}{L}+\frac{E(n-A-1)}{L}+……+\frac{E(n-B)}{L}+1 E(n)=LE(n−A)+LE(n−A−1)+......+LE(n−B)+1
特别地如果A=0，那么解方程即可：
E ( n ) = E ( n ) L + E ( n − 1 ) L + . . . . . . + E ( n − B ) L + 1 E(n)=\frac{E(n)}{L}+\frac{E(n-1)}{L}+……+\frac{E(n-B)}{L}+1 E(n)=LE(n)+LE(n−1)+......+LE(n−B)+1
E ( n ) = L L − 1 ∗ ( E ( n − 1 ) L + . . . . . . + E ( n − B ) L + 1 ) E(n)=\frac{L}{L-1}*(\frac{E(n-1)}{L}+……+\frac{E(n-B)}{L}+1) E(n)=L−1L∗(LE(n−1)+......+LE(n−B)+1)
对于以上两个方程，递推的时候利用E(n)的前缀和即可在O(n)的时间复杂度内递推出答案。
注意这里最好不要写成:
E ( n ) = E ( n ) + 1 L + E ( n − 1 ) + 1 L + . . . . . . + E ( n − B ) + 1 L E(n)=\frac{E(n)+1}{L}+\frac{E(n-1)+1}{L}+……+\frac{E(n-B)+1}{L} E(n)=LE(n)+1+LE(n−1)+1+......+LE(n−B)+1
上面的那种写法，当某个结点不存在时（比如E(-2)）依然满足（直接作为0处理就行），而这种写法从意义上就会出错。
这种不会回到之前状态的步数期望问题，直接列方程：当前点的期望于能转移到当前状态的期望的平均值加一，如果含有当前点本身解方程即可。
本文地址：https://blog.csdn.net/qq_45622214/article/details/110844232
