【计数】序列转等概率环问题

问题描述

有 \(m\) 个人要坐 \(n\) 个位置，每个人的选择方式如下。首先选择一个座位，选定一个方向（向左/右），然后找到从这个座位开始这个方向的第一个空座位。

如果这时走到尽头都选不到座位，就声称这个人失败了。

一个完美的方案当且仅当所有人都不失败，求完美方案数。

\(1 \leq m \leq n \leq 10^{18}\) 。

算法描述

这个问题叫做 序列转等概率环问题 。

考虑两端可以看做等价，所以可以加一个虚点 \(n + 1\) 将其看做一个环，每次可以选一个点顺时针或者逆时针走，要求最后不碰到 \(n + 1\) 。

直接将总方案数 \((2n + 2)^m\) 减去碰到 \(n + 1\) 的方案即可。

这是我们惊奇的发现，环状结构比链状结构好的一点是每个点等价，所以每个点被选的情况数是相同的，由于所有情况选的点数是 \(m(2n + 2)^m\) 。所以 \(n + 1\) 被选的情况就是 \(\frac {m(2n + 2)^m}{n + 1}\) 。

所以答案就是 \((2n + 2)^m(1 - \frac m{n + 1})\) 。

着实是一种很人类智慧的方法。