AGC007C Pushing Balls —— 期望的神题

Problem Link

题意： 序列上按顺序交错有 n" role="presentation">n$n$ 个球和 n+1" role="presentation">n+1$n+1$ 个洞，即 hole1,ball1,hole2,ball2,…,balln,holen+1" role="presentation">hole1,ball1,hole2,ball2,…,balln,holen+1$hol{e}_1,bal{l}_1,hol{e}_2,bal{l}_2,\dots ,bal{l}_n,hol{e}_{n+1}$，相邻两个位置的距离形成一个首项为 s" role="presentation">s$s$ 公差为 d" role="presentation">d$d$ 的等差数列，接下来有 n" role="presentation">n$n$ 次操作，每次操作会随机选一个球并将其随机向左推或向右推。容易发现最后每个球都会滚进一个洞中。求所有球滚动的总距离的期望。

发现 1：所谓的等差数列可以转化为每个距离都相同。

注意到对于任意一种推球的方式，考虑与它恰好对称的推球方式，可以发现，对于每个球来说，它们在两次推球的过程中走过距离的平均值为一定值 s+(n−1)/2∗d" role="presentation">s+(n−1)/2∗d$s+(n-1)/2\ast d$！于是可以认为每相邻两个位置的距离均为此定值。

发现 2：对于各种情况，可以将每个位置的距离取期望后再进行计算。

注意到总期望距离可认为 ∑statepstatediti=∑iE[i]ti" role="presentation">∑statepstatediti=∑iE[i]ti$\sum _{state}{p}_{state}{d}_i{t}_i=\sum _{i}E[i]t_i$，其中 ti" role="presentation">ti$t_i$ 为每个状态中 i" role="presentation">i$i$ 被覆盖的次数，pstate" role="presentation">pstate$p_{state}$ 为状态 state" role="presentation">state$state$ 出现的概率，di" role="presentation">di$d_i$ 为该状态中空隙 i" role="presentation">i$i$ 的距离。于是这个距离可以期望化。

通过以上两个发现，可以注意到每次操作后仍然可以转化为每个空隙都有一个期望，发现除了首尾以外所有空隙期望长度均相同，且首尾两个空隙平均下来也是对的，就可以视为所有位置长度都相同，随便推推狮子即可。

时间复杂度 O(n)" role="presentation">O(n)$O(n)$。

本题两个发现可谓精妙绝伦啊~~~