销毁的期望时间：题解

思路

把初始元素看作按行排列的块，第 $i$ 个块位于列 $S_i$，并在第 $n+1$ 行、列 $m+1$ 放一个静止哨兵。一次随机操作等价于随机选择一个尚未与下一行块相接的连通块并向右移动。

由期望的线性性，总时间等于每个块追上下一行块所需移动次数期望之和。只考虑一对块：前块在 $i$、后块在 $j$。记 $dp_{i,j}$ 为前块消失前自身移动次数的期望。

边界为

当 $i<j\le m$ 时，两块各以 $1/2$ 的概率移动；只有前块移动时计一次，因此

把 $S_{n+1}=m+1$，答案就是 $\sum_{x=1}^n dp_{S_x,S_{x+1}}$。

做法

• 子任务 1：对集合位掩码做记忆化期望搜索，直接枚举随机选择的元素。
• 子任务 2：对每一对相邻初始块分别重建二维 DP，复杂度 $O(nm^2)$。
• 子任务 3：只构建一次包含所有 $(i,j)$ 的 DP 表，复杂度 $O(m^2)$。

正确性证明

引理 1：整个过程的总操作数等于所有真实块在追上下一行块前的自身移动次数之和。

每次操作恰使一个当前连通块右移一次；将该次移动记在这个连通块最上方尚未消失的真实块上。每次操作被记一次，每个真实块的记录直到追上下一块为止。

引理 2：递推式正确给出一对块中前块的期望移动次数。

相遇时期望为零；后块已在哨兵列时只能前块移动。其余状态两块等概率移动，前块分支额外贡献一次自身移动，取条件期望即得递推。

定理：算法输出集合变空所需时间的期望。

由引理 1 和期望线性性，总期望是各相邻块对贡献之和；由引理 2，每项均由 DP 正确计算，所以答案正确。

复杂度

时间复杂度 $O(m^2+n)$，空间复杂度 $O(m^2)$。