AGC007C Pushing Balls —— 期望的神題
題意： 序列上按順序交錯有 \(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)\)。
本題兩個發現可謂精妙絕倫啊~~~
