# 一道有趣的计数问题

Author: Fanyi Pu

Published: 2019-02-23

Canonical: <https://pufanyi.com/blog/oi-icpc/other-problems/chocolate-counting>

巧克力切割收益的期望计数问题。

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

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

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

![](https://pufanyi.com/posts/oi-icpc/other-problems/chocolate-counting/%E6%A0%BC%E5%AD%90.avif)

如果一个点“暴露在了外面”，即该点对应的方块成为了整个方块的左下角，那么之后每切一次它就会对答案有 $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)$ 算法。