問題一覧 > 通常問題

No.2245 Second Smallest

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : noya2 / テスター : shobonvip 👑 Nachia
お気に入りにしたユーザー ProblemId : 9050 / 自分の提出
問題文最終更新日: 2023-03-10 01:28:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 380 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$. In each cell $(i,j)$, a real number between $0$ and $1$, inclusive, is written, chosen uniformly at random and independently for each cell.

noya is at cell $(1,1)$ and wants to reach cell $(H,W)$ by repeatedly moving to the cell adjacent to the right or below. Let $x$ be the $2$-nd smallest real number, counting duplicates, among the real numbers written on the cells passed through (including $(1,1),(H,W)$). Then the score noya gets is $x^K$.

When noya moves so that the score of the path is as small as possible, find the expected value of the score $\bmod 998244353$. (See Notes.)

Notes

It can be proved that the expected value to be found is always a rational number. Moreover, under the constraints of this problem, it can be proved that, when this value is expressed as $\dfrac{P}{Q}$ using $2$ coprime integers $P,Q$, there exists exactly one integer $R$ satisfying $R\times Q\equiv P\pmod{998244353}$ and $0\le R\lt 998244353$. Find this $R$.

Constraints

  • All input values are integers
  • $2\le H,W\le 3\times 10^4$
  • $1\le K\le 3\times 10^4$

Input

$H$ $W$ $K$

Output

Find the expected value of the score noya gets $\bmod 998244353$ and print it.

Sample

Sample 1
Input
2 2 1
Output
632221424

The expected value to be found is $\dfrac{13}{30}$.

Sample 2
Input
3 4 2
Output
764290182

The expected value to be found is $\dfrac{214}{5005}$.

Sample 3
Input
314 159 265
Output
369907178

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。