No.2245 Second Smallest
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
Nachia