Link.
Description.
有 \(m\) 个人，轮流占位置，第 \(i\) 个人出现在 \(a_i\) 并往 左/右 方向移动，占领第一个没有人的位置。
其中 \(a_i\in[1,n]\)，统计 没有人没有座位的 方案。
Solution.
首先新加一个位置 \(n+1\) 并认为它在 \(1\) 左边且在 \(n\) 右边，成环了。
我们需要统计的方案数是每个人来到 \(1\cdots n\) 且 \(n+1\) 没被占掉的方案数。
不妨假设人们可以来到 \(n+1\)，如果来了 \(n+1\) 必然被占据了，所以方案数相同。
总方案数就成了 \((2(n+1))^m\)，而且每个位置本质相同，被占掉的概率相同。
所以第 \(n+1\) 个位置没被占掉的概率是 \(\frac{n+1-m}{n+1}\)。
所以答案就是 \(2^m\cdot(n+1-m)\cdot(n+1)^{m-1}\)
Coding.
点击查看 /ruo 代码
别吧别吧这种题还要看代码？？？