AT_abc297_f [ABC297F] Minimum Bounding Box 2

题目描述

有一个高 $H$ 行、宽 $W$ 列的网格。

从这个网格中等概率随机选择 $K$ 个格子。将所有被选中的格子包含在内的、边与网格轴平行的最小矩形中，包含的格子数作为得分。

请你求出最终得分的期望值，并对 $998244353$ 取模。

有理数 $\bmod\ 998244353$ 的含义如下：可以证明，所求的期望值一定是有理数。在本题的约束下，设该值可以表示为互质的两个整数 $P$、$Q$，即 $\frac{P}{Q}$。请你输出唯一满足 $R\times Q\equiv P\pmod{998244353}$ 且 $0\leq R<998244353$ 的整数 $R$。

输入格式

输入从标准输入读入，格式如下：

$H$ $W$ $K$

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 2 2

输出 #1

665496238

输入输出样例 #2

输入 #2

10 10 1

输出 #2

1

输入输出样例 #3

输入 #3

314 159 2653

输出 #3

639716353

说明/提示

约束条件

• $1\leq H,W\leq 1000$
• $1\leq K\leq HW$
• 输入均为整数

样例解释 1

如果选择了格子 $(1,1)$ 和 $(2,2)$，或者选择了格子 $(1,2)$ 和 $(2,1)$，这两种情况下得分为 $4$。除此之外的 $4$ 种情况得分为 $2$。因此，期望得分为 $\frac{4\times 2 + 2\times 4}{6} = \frac{8}{3}$，而 $665496238\times 3\equiv 8\pmod{998244353}$，所以答案为 $665496238$。

由 ChatGPT 4.1 翻译