一道有趣的计数问题

给你一块巧克力，横着最多切 $a$ 刀，竖着最多切 $b$ 刀，定义每切一刀的收益为切完后所有巧克力的和，每次随机在能切的所有地方等概率随机切一刀，求切 $k (k \leq a + b)$ 到刀得到收益的期望。答案对 $998244353$ 取模。

$a, b \leq 10^{18}$ 。

我们考虑每个正方形左下角（如下图）为贡献，如黄色格子的贡献我们看成是点 $P$ 的贡献，那我们可以把点分成三类：中间的（红色点），边缘的（蓝色点），左下角的（绿色点）。

如果一个点“暴露在了外面”，即该点对应的方块成为了整个方块的左下角，那么之后每切一次它就会对答案有 $1$ 的贡献。

首先我们来看中间的点（红点）。

对于每个点，如果第 $i$ 次切割后它暴露在外面，那么前 $i$ 次切割必定有一次切了它所在竖列，还有一次且了它所在横行。所以有 $(\binom{i}{2})$ 中排列方案。而从这么多横行于纵列中选 $2$ 条线的方案数为 $(\binom{a + b}{2})$ ，所以第 $i$ 次切完后该点暴露在外面的概率为：

E (i) = \frac{(\binom{i}{2})}{(\binom{a + b}{2})}

由于切了 $k$ 次，所以每个点贡献的期望为：

\sum_{i = 1}^{k} E (i) = \sum_{i = 1}^{k} \frac{(\binom{i}{2})}{(\binom{a + b}{2})} = \frac{\sum_{i = 1}^{k} (\binom{i}{2})}{(\binom{a + b}{2})} = \frac{(\binom{k + 1}{3})}{(\binom{a + b}{2})} = \frac{\frac{(k + 1) \cdot k \cdot (k - 1)}{6}}{\frac{(a + b) (a + b - 1)}{2}} = \frac{(k + 1) \cdot k \cdot (k - 1)}{3 \cdot (a + b) \cdot (a + b - 1)}

总共有 $a b$ 个红点，所以总的期望为：

\frac{(k + 1) \cdot k \cdot (k - 1)}{3 \cdot (a + b) \cdot (a + b - 1)} \cdot a b

然后是边上的点（蓝点）。

每次切都会多一个蓝点，所以贡献一定为：

\sum_{i = 1}^{k} i = \frac{k (k + 1)}{2}

最后是左下角的绿点，每次切都会它都会有 $1$ 的贡献，所以是 $k$ 。

所以总的贡献为：

\frac{(k + 1) \cdot k \cdot (k - 1) \cdot a b}{3 \cdot (a + b) \cdot (a + b - 1)} + \frac{k \cdot (k + 1)}{2} + k

优秀的 $O (1)$ 算法。

Cite this post