自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:22:20，当前版本为作者最后更新于2020-06-06 18:04:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd：很抱歉最后一个式子打错了，现已修复。

首先容易发现性质：两个球经过 $t$ 时间若在同一位置，当且仅当它们的瞬移次数模 2 同余。

那么枚举题目中选择的时刻（即二元组中的 $j$，为了方便这里记为 $k$），讨论两个球在同一位置时瞬移的次数：

$$\text{even}_k=\sum_{i=0}^k \binom kip^i(1-p)^{k-i}[i \bmod 2 = 0] $$$$\text{odd}_k =\sum_{i=0}^k \binom kip^i(1-p)^{k-i}[i \bmod 2 = 1] $$

算出的就是在 $k$ 时刻瞬移次数分别为 奇数/偶数 的概率。
于是直接得到答案计算式：

$$\text{ans} = \frac{1}{2n} \frac{1}{t+1}\sum_{k=1}^{t+1} \text{even}_k^2+\text{odd}_k^2 $$

（这里枚举从 $1 \sim k+1$ 是因为，题目中的零时刻也可以瞬移，而这里的 $k$ 实际上是瞬移次数上限）

注意到上面两个式子很像二项式展开，考虑拆 $[i \bmod 2 = 0]$ 为 $(1+(-1)^i)/2$：

$$\text{even}_k= \sum_{i=0}^k \binom kip^i(1-p)^{k-i}[2|i] $$$$= \frac 12\sum_{i=0}^k \binom ki p^i(1-p)^{k-i}(1+(-1)^i) $$$$= \frac 12\left( \sum_{i=0}^k \binom kip^i(1-p)^{k-i}+\sum_{i=0}^k\binom ki(-p)^i(1-p)^{k-i} \right) $$$$= \frac 12(1+(1-2p)^k)$$

类似地也能得到

$$\text{odd}_k= \frac 12(1-(1-2p)^k)$$

把平方展开，答案就很明显了：

$$\text{ans} = \frac{1}{2n}\frac{1}{t+1}\sum_{k=1}^{t+1} \frac{1+(1-2p)^{2k}}{2} $$

等比数列求和即可，时间复杂度 $\Theta(\log n + \log t)$。