/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦 H 行、横 W 列のグリッドがあります。
このグリッドから一様ランダムに K 個のマスを選びます。選んだマスを全て含むような（グリッドの軸に辺が平行な）最小の長方形に含まれるマスの個数がスコアとなります。
得られるスコアの期待値を \text{mod }998244353 で求めてください。
有理数 \text{mod }998244353 とは
求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。制約
- 1\leq H,W \leq 1000
- 1\leq K \leq HW
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W K
出力
答えを出力せよ。
入力例 1
2 2 2
出力例 1
665496238
マス (1,1) とマス (2,2) が選ばれた場合、またはマス (1,2) とマス (2,1) が選ばれた場合の 2 通りではスコアは 4 となります。また、それ以外の 4 通りではスコアは 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
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