3/20 联考 T2 Bridge 题解

题意简述

有 个人在数轴上等速移动，每个人有一个初始方向，两人相遇时，有 的概率左边的人会消失， 的概率右边的人会消失，求最终恰有 个人抵达数轴最左端， 个人抵达数轴最右端的概率。

复杂度要求 。

题解

首先，我们找到最靠右的抵达数轴左端点的人 ，那么最靠左的抵达数轴右端点的人一定在他的右边，且一定恰是 。简单分类讨论易证。

接下来，我们枚举 所在的位置，分别求其左侧恰有 个人存活以及其右侧恰有 个人存活的概率再相乘，最终将所有位置的答案相加即可。

由于对于任何一个区间内的人，他一定会先与区间内的人发生碰撞，所以我们可以优先考虑任何一个区间当中发生的碰撞事件；同时又由于一个人只会与异向的人发生碰撞，而一个人存活的概率只需要计算他在所有碰撞当中存活下来的概率之乘积，所以我们在扩展区间的时候只需要关心这一区间内的所有碰撞后向左/向右的人还剩下多少。

以 左侧为例，考虑一个简单 ：我们设 表示区间 中的人互相碰撞完成后，恰好有 个向左的人存活下来的概率。借助简单分类讨论即可写出转移方程，使用前缀和优化将复杂度降低至 。然而这并不足以通过此题，考虑进一步优化。

事实上，这个 复杂度难以进一步降低的原因在于枚举 。同时，我们发现最终状态永远都是 ，我们的起始状态有 个，而终止状态只有 个，每次 都会求出大量无用信息，这就造成了很大的浪费。因此考虑反转整个 过程，尝试求出对于每一个 ，其两侧分别能成功抵达最终状态的概率。设 表示区间 （我们并不知道 在哪里，只知道 ）中的人互相碰撞完成后，恰好有 个向左的人存活下来，这一状态能够最终抵达 的概率。转移如下：

• 为朝左：直接满足条件，。
• 为朝右：枚举 击败了多少个人（注意， 不可能将其右侧的所有朝左的人击败，这样的话 本身就位于 右侧，所以 下标从 开始），。

时间复杂度成功降低至 。