一道有趣的计数问题

pufanyi

随笔

发布于：Feb 23, 2019

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

$a, b\le 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)}$$

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

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

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

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

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

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

所以总的贡献为：

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

优秀的 $\mathcal{O}(1)$ 算法。

更新于：Jul 7, 2023

数学

模拟赛