CF#688 D. CheckpointsCF #688D
CF #688D原题链接题意：构造一串长为n的01序列(n≤2000)(n\leq 2000)(n≤2000)，有12\frac1221的概率成功通过第i个关卡，如果失败，立即返回到小于等于i的最大的1位置。为何单独一个1，通过的期望次数是2呢？我们假设穿过一个单独的1的期望是x有12\frac1221的概率一次通过，也有12\frac1221的概率失败，那么还需要x的期望通过。于是x=12∗1+12∗(x+1)x=\frac12*1+\frac12*(x+1)x=21∗1+21∗(x
