似乎上一篇有一点长了，换一篇罢。
2022.11.14
\(\textrm{AtCoder [AGC007C] Pushing Balls}\)
观摩了一下题解，挺好的
首先考虑到第一条边、倒数第一条边经过次数的期望是一样的，所以两条边的长度可以先折个中，取 \(\frac{2d+(2n-1)x}{2}\)，影响不大。
似乎所有边都可以这样考虑，并且边数为偶数诶。
那么问题就变成了求 \(d = 1, x = 0\) 情况的解，再乘上一个 \(\frac{2d+(2n-1)x}{2}\)。
现在我们想求第 \(i\) 次移动的球的移动长度期望，相当于求已经进行 \(i-1\) 次移动后线段长度的期望。
没有移动之前，线段长度的期望为 \(E_0 = 1\)。
接下来第 \(i\) 次，都有 \(\frac{1}{n+1-i}\) 的概率删去一条线段，\(\frac{n-i}{n+1-i}\) 的概率合并两条线段。
可得：\(E_i = \frac{n-i}{n+1-i}E_{i-1}\)。
所以：\(E_i = \frac{n+1}{n+1-i}\)。
答案即为：\(\frac{2d+(2n-1)x}{2}\times\sum\limits_{i = 2}^{n+1}\frac{n+1}{i}\)。
标签：frac,水题,线段,2d,徒步,长度,期望,2n,2.0 From： https://www.cnblogs.com/bikuhiku/p/hiking_delightly.html