【题解】CF838D Airplane Arrangements 题解

题意

一架飞机有 $n$ 个座位排成一列，有 $m$ 名乘客依次上飞机。
乘客乘客会选择一个目标座位（同一个目标座位可以被多个人选择），然后选择从前门或者后门上飞机，上飞机后，他们会走到自己的目标座位，如果目标座位已经有人坐了，他们会继续往前走，在走到第一个空位后坐下。如果走到最后还没有找到座位，这名乘客就会生气。
问有多少种登机方案能让所有乘客都不生气，输出方案数对 $10^9+7$ 取模后的结果。两个登机方案不同当且仅当第 $i$ 位乘客的目标座位或上飞机走的门不同。
$\mathcal{Data~Range}$ ： $1 \le m \le n \le 10^6$ 。

题解

妙妙题。

首先进行一步转化：把前门和后门一起看作第 $n + 1$ 个座位，这样所有座位将会呈一个有 $n + 1$ 个节点的环。

我们考虑一种方式，将每一种原方案与每一种环上方案一一对应：把从前门进和从后门进分别转化为从环上的 $n + 1$ 号节点开始顺时针走和逆时针走，并将环上方案不合法的条件设为有人走到了 $n + 1$ 号节点上。那么，我们的任务也就转化为统计有多少环上方案使得没有人走到 $n + 1$ 号节点上。

然而这样转化还不能解决本题，因为环上方案暂时不存在比较优秀的性质。因此，我们还需加上一条限制：令 $n + 1$ 号节点同样为可供选择的位置。可以发现，加上这条限制后，不仅每一种原合法方案和每一种环上合法方案仍然能够一一对应，而且我们得到了一个十分优秀的性质：环上的每一个节点都是等价的。

于此本题的解法便呼之欲出了。我们不妨设每一个节点最终被走到的概率均为 $p$ ，那么由于被走到的节点总数为 $m$ ，若我们将其看做期望，则根据期望的线性性，有 $p \cdot (n+ 1) = m$ ，即 $p = \dfrac{m}{n +1}$ ，而概率 $p$ 反映的实际上就是不合法方案的占比，因此答案即为总方案数乘上 $1 - p$ 。总方案数并不难得出，为 $2^m \cdot (n+ 1)^m$ 。