CF688div2 1453D. Checkpoints(期望递推构造)
题意构造一串长nnn的零一序列(n<=2000)(n<=2000)(n<=2000)有12\frac{1}{2}21的概率成功通过第iii个关卡如果失败,立刻返回小于等于iii的最小的111位置观察发现如果单独一个111,穿过去的期望步数是222如果要算也很简单,设穿过一个单独的111的期望是xxx有12\frac{1}{2}21的概率一步穿过,12\frac{1}{2}21的概率一步失败,还需要期望xxx通过那么x=12∗1+12∗(x+1)x=
