F - Minimum Bounding Box 2

Contest Duration: 2023-04-09(Sun) 12:00 - 2023-04-09(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Minimum Bounding Box 2 Editorial

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$

出力

答えを出力せよ。

入力例 1Copy

Copy

2 2 2

出力例 1Copy

Copy

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$ が答えとなります。

入力例 2Copy

Copy

10 10 1

出力例 2Copy

Copy

入力例 3Copy

Copy

314 159 2653

出力例 3Copy

Copy

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 1Copy

Copy

2 2 2

Sample Output 1Copy

Copy

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 2Copy

Copy

10 10 1

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

314 159 2653

Sample Output 3Copy

Copy

639716353