Minimum Bounding Box 2

题目描述

我们有一个 $H$ 行 $W$ 列的网格。 我们从该网格中均匀随机地选择 $K$ 个格子。分数是包含所有被选格子的最小矩形（其边与网格轴平行）中的格子数。 求期望分数对 $998244353$ 取模的值。

输入格式

输入由标准输入按如下格式给出： $H$ $W$ $K$

输出格式

输出答案。

2 2 2

665496238

10 10 1

1

314 159 2653

639716353

提示

$1\leq H,W \leq 1000$ $1\leq K \leq HW$ 输入中的所有值均为整数。在下述两种情况下分数等于 $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$。

标签: AtCoder|abc297F

来源

AtCoder|abc297F