Problem Link
题意： 序列上按顺序交错有 \(n\ 个球和 \(n+1\ 个洞，即 \(hole_1,ball_1,hole_2,ball_2,\dots,ball_n,hole_{n+1}\，相邻两个位置的距离形成一个首项为 \(s\ 公差为 \(d\ 的等差数列，接下来有 \(n\ 次操作，每次操作会随机选一个球并将其随机向左推或向右推。容易发现最后每个球都会滚进一个洞中。求所有球滚动的总距离的期望。
发现 1：所谓的等差数列可以转化为每个距离都相同。
考虑与它恰好对称的推球方式，可以发现，对于每个球来说，它们在两次推球的过程中走过距离的平均值为一定值 \(s+(n-1/2*d\！于是可以认为每相邻两个位置的距离均为此定值。
发现 2：对于各种情况，可以将每个位置的距离取期望后再进行计算。
\(\sum_{state} p_{state}d_it_i=\sum_i E[i]t_i\，其中 \(t_i\ 为每个状态中 \(i\ 被覆盖的次数，\(p_{state}\ 为状态 \(state\ 出现的概率，\(d_i\ 为该状态中空隙 \(i\ 的距离。于是这个距离可以期望化。
时间复杂度 \(O(n\。
本题两个发现可谓精妙绝伦啊~~~