102975: [Atcoder]ABC297 F - Minimum Bounding Box 2
Description
Score : $500$ points
Problem Statement
We have a grid with $H$ rows and $W$ columns.
We choose $K$ cells in this grid uniformly at random. The score is the number of cells in the minimum rectangle (whose edges are parallel to the axes of the grid) that contains all of the chosen cells.
Find the expected score modulo $998244353$.
What is rational number modulo $998244353$?
We can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as $\frac{P}{Q}$ by two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find such $R$.Constraints
- $1\leq H,W \leq 1000$
- $1\leq K \leq HW$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$H$ $W$ $K$
Output
Print the answer.
Sample Input 1
2 2 2
Sample Output 1
665496238
The score equals $4$ in the following two cases: if cells $(1,1)$ and $(2,2)$ are chosen, or cells $(1,2)$ and $(2,1)$ are chosen. The other four cases yield a score of $2$.
Thus, the expected score equals $\frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3}$. Since $665496238 \times 3 \equiv 8\pmod{998244353}$, you should print $665496238$.
Sample Input 2
10 10 1
Sample Output 2
1
Sample Input 3
314 159 2653
Sample Output 3
639716353
Input
题意翻译
在一个 $H$ 行 $W$ 列的网格图上随机选择 $K$ 个点。定义当前局面的分数为最小的可以围住这 $K$ 个点的矩形的面积。 请求出所有局面中分数的期望值，输出时对 $998244353$ 取模。Output
问题描述
我们有一个包含H行和W列的网格。
我们在这个网格中随机选择K个单元格。分数是最小矩形（其边缘与网格的轴平行）中的单元格数，该矩形包含所有选择的单元格。
求期望的分数模998244353。
什么是998244353的有理数模？
我们可以证明所求期望值总是有理数。 此外，在本问题的约束下，当值表示为由互质整数P和Q表示的$\frac{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