题解

思路

最终被占用的座位会形成若干连续段。对一个恰好坐满的长度为 $i$ 的段，枚举最后入座者最终坐在第 $k$ 个位置，左右两部分互不影响；对没有坐满的座位前缀，则枚举最右侧坐满段的长度。分别维护合法方案数 $G$ 和距离总和 $F$ 即可。

做法

子任务 1

递归枚举每位参赛者的 $n$ 个目标位置和两个方向，直接模拟寻找空位，只累加合法方案。复杂度为 $O((2n)^m mn)$。

子任务 2

用二进制集合表示已占用座位。状态同时维护到达该集合的方案数和距离总和；枚举下一人的目标与方向并转移。复杂度为 $O(mn2^n)$。

子任务 3

令 $G_{i,j}$ 表示 $j$ 人坐进 $i$ 个座位的合法方案数，有闭式

$$G_{i,0}=1,\qquad G_{i,j}=2(i+1-j)\,[2(i+1)]^{j-1}.$$

令 $F_{i,j}$ 表示这些方案的疯狂值总和。

当 $i=j$ 时，枚举最后一人最终坐在第 $k$ 位。左右方案数为 $G_{k-1,k-1}G_{i-k,i-k}\binom{i-1}{k-1}$；最后一人的全部距离贡献为 $\binom{k}{2}+\binom{i-k+1}{2}$，左右已有贡献还需乘最后一人的目标与方向选择数 $i+1$。

当 $i>j$ 时，枚举最右侧坐满段长度 $k$。若 $k=0$，对应 $F_{i-1,j}$；若 $k>0$，把左侧未满部分与长度 $k$ 的满段合并，并乘选择进入该满段的 $k$ 位参赛者的组合数 $\binom jk$。

按 $i$ 递增即可得到 $F_{n,m}$。

复杂度

三个子任务时间复杂度依次为 $O((2n)^m mn)$、$O(mn2^n)$、$O(nm^2+n^2\log p)$；空间复杂度依次为 $O(n)$、$O(2^n)$、$O(nm)$。

正确性说明

满段递推按最后入座者的最终位置唯一划分方案，左右部分独立且组合数恢复原到场顺序；距离贡献分为最后一人新增部分与左右继承部分。未满递推按最右连续满段唯一划分，分别合并方案数与已有距离总和。两类划分互斥且覆盖全部合法方案，因此动态规划恰好累加每个合法数组对一次。