分数: 500 点
问题陈述
我们有一个网格 H 行和 W 列。
我们选择 K 该网格中的单元格均匀随机。 分数是包含所有选定单元格的最小矩形(其边缘平行于网格的轴)中的单元格数量。
求期望分数模数 998244353.
什么是有理数模 998244353?
我们可以证明所求的期望值始终是有理数。 而且,在这个问题的约束下,当值表示为 \frac{P}{Q} 由两个互质整数 P 和 Q,我们可以证明有一个唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。 找到这样的 R.约束
- 1\leq H,W \leq 1000
- 1\leq K \leq HW
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W K
输出
打印答案。
示例输入 1
2 2 2
示例输出 1
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.
示例输入 2
10 10 1
示例输出 2
1
示例输入 3
314 159 2653
示例输出 3
639716353