题解

思路

把初始的 $n+m-2$ 条裁剪线随机排列，并按排列顺序尝试；已经随纸片丢弃的线直接跳过。这与每一步在当前仍存在的线中等概率选择完全等价。

令 $K=k-1$。一次操作前面积仍不小于 $k$，等价于当前高宽之积大于 $K$。利用期望的线性性，期望操作数等于每条线在终止前被实际裁到的概率之和。

做法

子任务 1

设 $E(h,w)$ 为从 $h\times w$ 开始的期望。若 $hw<k$，则为零；否则枚举所有下一刀并递归：

$$E(h,w)=1+\frac{\sum_{x=1}^{w-1}E(h,x)+\sum_{y=1}^{h-1}E(y,w)}{h+w-2}.$$

直接按面积递增计算，并逐项求和，复杂度为 $O(nm(n+m))$。

子任务 2

上述转移中的两段和分别是同一行和同一列的前缀和。维护行前缀与列前缀即可把每个状态降为 $O(1)$，总复杂度 $O(nm)$。

子任务 3

考虑水平线 $y=i$。它会被实际裁到，当且仅当它在所有更靠上的 $i-1$ 条水平线，以及会让当前宽度不超过 $\min(\lfloor K/i\rfloor,m)$ 的那些竖直线之前出现。若 $j=\min(\lfloor K/i\rfloor,m)$，且 $j<m$，相关线共有 $i+j$ 条，所以该水平线最先出现的概率是 $1/(i+j)$；若 $j=m$，到达它之前面积已经会小于 $k$，贡献为零。竖直线同理。

当初始面积不小于 $k$ 时，最终使过程终止的那一刀必然贡献 $1$。因此答案为 $1$，再加上两类未终止裁剪线的上述概率。预处理 $1$ 到 $2\cdot10^6$ 的模逆元即可。

复杂度

三档算法时间复杂度依次为 $O(nm(n+m))$、$O(nm)$、$O(n+m)$；空间复杂度依次为 $O(nm)$、$O(nm)$、$O(n+m)$。

正确性说明

随机排列模型中，每一步尚存裁剪线的相对顺序仍是均匀随机排列，故与原过程同分布。对子任务 1、2，递推枚举了每条等概率下一刀，并在面积首次小于 $k$ 时停止，因此由全期望公式正确。满分算法对每条线准确计算了它在所有能令其提前消失或令过程提前终止的相关线中最先出现的概率；期望线性性允许直接相加，不要求这些事件独立。再计入必然发生的终止刀，所得即为期望裁剪次数。