Ela 去远足：题解

记第 $i$ 个初始位置的蚂蚁最终存活的概率为 $p_i$，并令

$$S_i=\sum_{j=i}^{n}p_j.$$

以下所有运算均在模 $10^9+7$ 意义下进行。

思路

当 $n=1$ 时，显然 $p_1=1$。下面假设 $n>1$。

最左侧蚂蚁不可能成为最终存活者，因此 $p_1=0$。从运动过程可以得到如下关键结论：

1. 最右侧蚂蚁存活，当且仅当决定它命运的 $\lfloor(n-1)/2\rfloor$ 个独立方向选择均取到指定方向，因此

   $$p_n=2^{-\lfloor(n-1)/2\rfloor}.$$

2. 对 $2\le i<n$，位置 $i$ 的蚂蚁首先需要通过 $\lfloor(i+1)/2\rfloor$ 个独立、等概率的方向条件；在这些条件成立后，唯一会阻止它存活的事件是最终存活者来自位置 $2i,2i+1,\ldots,n$。这些事件互斥，故

   $$p_i=2^{-\lfloor(i+1)/2\rfloor} \left(1-\sum_{j=2i}^{n}p_j\right).$$

   若 $2i>n$，括号内的和为空，视为 $0$。

这个递推只依赖更大的下标。按 $i=n,n-1,\ldots,2$ 倒序计算，并维护后缀和 $S_i$，即可在常数时间内求出每个 $p_i$：

$$p_i=2^{-\lfloor(i+1)/2\rfloor}(1-S_{2i}),\qquad S_i=S_{i+1}+p_i.$$

做法

1. 若 $n=1$，直接输出 $1$。
2. 否则令 $p_1=0$，按公式初始化 $p_n$ 和 $S_n$。
3. 从 $n-1$ 到 $2$ 倒序枚举 $i$。若 $2i\le n$，用已计算的 $S_{2i}$ 修正 $p_i$；随后更新 $S_i$。
4. 依次输出 $p_1$ 到 $p_n$。

正确性证明

下面证明算法输出的每个概率均正确。

引理 1：当 $n>1$ 时，$p_1=0$，且 $p_n=2^{-\lfloor(n-1)/2\rfloor}$。

由蚂蚁碰撞中“同重时向左者获胜”的规则，最左侧蚂蚁无法在仍有其他蚂蚁时赢得最终碰撞，所以 $p_1=0$。对最右侧蚂蚁，沿其向左扩张的碰撞链，每隔一个初始位置产生一个独立的必要方向条件；共有 $\lfloor(n-1)/2\rfloor$ 个，且每个成立概率为 $1/2$，故结论成立。

引理 2：对任意 $2\le i<n$，

$$p_i=2^{-\lfloor(i+1)/2\rfloor}(1-S_{2i}).$$

位置 $i$ 的蚂蚁必须先满足 $\lfloor(i+1)/2\rfloor$ 个独立方向条件，其概率为相应的 $2$ 的负幂。条件成立后，位置小于 $2i$ 的其他蚂蚁都不能越过它成为最后存活者；失败恰好发生在最终存活者的初始位置至少为 $2i$ 时。最终存活位置唯一，所以这些失败事件互斥，总概率为 $S_{2i}$。将两部分相乘即得递推式。

定理：算法输出的 $p_1,p_2,\ldots,p_n$ 是各初始位置蚂蚁最终存活的概率。

算法先由引理 1 正确计算边界。随后按下标递减计算；求 $p_i$ 时，所有 $p_j(j>i)$ 及所需后缀和已经正确。由引理 2，算得的 $p_i$ 也正确。归纳可知所有输出均正确。

复杂度分析

每组测试的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。所有测试的 $n$ 之和不超过 $10^6$。