#AT2538. F - Minimum Bounding Box 2
F - Minimum Bounding Box 2
当前没有测试数据。
F - 最小边界框2
得分： 500 分
问题描述
我们有一个$H$行$W$列的网格。
我们在该网格中以均匀随机方式选择$K$个单元格。分数是包含所有选择的单元格的最小矩形（其边与网格的坐标轴平行）中的单元格数。
求期望分数模$998244353$的余数。
什么是模$998244353$的有理数？
我们可以证明，所求期望值总是一个有理数。 此外，在该问题的约束下，当该值用两个互质整数和表示为时，我们可以证明存在唯一的整数使得且。找到这样的。
约束
- $1\leq H,W \leq 1000$
- $1\leq K \leq HW$
- 输入中的所有值均为整数。
输入
从标准输入中按以下格式给出：
输出
输出答案。
2 2 2
665496238
在以下两种情况下得分为$4$：如果选择单元格$(1,1)$和$(2,2)$，或选择单元格$(1,2)$和$(2,1)$。其他四种情况得分为$2$。
因此，期望分数等于$\frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3}$。由于$665496238 \times 3 \equiv 8\pmod{998244353}$，应该输出$665496238$。
10 10 1
1
314 159 2653
639716353