题解 CF838D 【Airplane Arrangements】

Soulist · 2020-07-14 19:38:05 · 题解

好仙的题啊 TAT

直接计数非常困难，我们考虑转换，假想每个人随机指定一个位置并开始走，求最后合法的概率。

然而这样计算仍然非常困难，注意到每个人可以往左走也可以往右走，我们将之想象成在一个 1\to n 的环上『顺时针』/『逆时针』走，然而这样无法表示非法的情况，考虑在 1 与 n 的接口处增加一个位置 n+1，那么如果这个位置被占据了就说明状态非法，否则均合法。

于是我们只需要统计给一个 n+1 的环分配 m 个人任意走最后使得 n+1 没有被占据的概率即可，如果认为初始可以配置在 n+1 处，那么显然在这个环上的每个位置都是等价的，所以概率均相同，于是一个位置被占据的概率为 \frac{m}{n+1}，可以得到答案发生的概率为 \frac{n+1-m}{n+1}，乘以方案数 (2\times (n+1))^m 即可。