E - Kth Number

Contest Duration: 2023-03-25(Sat) 12:00 - 2023-03-25(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Kth Number Editorial

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$0$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ があります。

今からすぬけくんが以下の操作 1, 2 を順に行います。

$A_i=0$ を満たすそれぞれの $i$ について、 $1$ 以上 $M$ 以下の整数を独立かつ一様ランダムに選び、 $A_i$ をその整数で置き換える。
$A$ を昇順に並び替える。

すぬけくんが操作 1, 2 を行ったあとの $A_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$ がただ $1$ つ存在することが証明できます。この $R$ を出力してください。

制約

$1\leq K \leq N \leq 2000$
$1\leq M \leq 2000$
$0\leq A_i \leq M$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$   $K$ 
 $A_1$   $A_2$   $\dots$   $A_N$

出力

すぬけくんが操作 1, 2 を行ったあとの $A_K$ の期待値を $\text{mod } 998244353$ で出力せよ。

入力例 1Copy

Copy

3 5 2
2 0 4

出力例 1Copy

Copy

すぬけくんは操作 1 において $A_2$ を $1$ 以上 $5$ 以下の整数で置き換えます。この整数を $x$ とすると、

$x=1,2$ のとき、すぬけくんが操作 1, 2 を行ったあと $A_2=2$ です。
$x=3$ のとき、すぬけくんが操作 1, 2 を行ったあと $A_2=3$ です。
$x=4,5$ のとき、すぬけくんが操作 1, 2 を行ったあと $A_2=4$ です。

よって、 $A_2$ の期待値は $\frac{2+2+3+4+4}{5}=3$ です。

入力例 2Copy

Copy

2 3 1
0 0

出力例 2Copy

Copy

221832080

期待値は $\frac{14}{9}$ です。

入力例 3Copy

Copy

10 20 7
6 5 0 2 0 0 0 15 0 0

出力例 3Copy

Copy

617586310

Score : $500$ points

Problem Statement

We have a sequence of length $N$ consisting of integers between $0$ and $M$ , inclusive: $A=(A_1,A_2,\dots,A_N)$ .

Snuke will perform the following operations 1 and 2 in order.

For each $i$ such that $A_i=0$ , independently choose a uniform random integer between $1$ and $M$ , inclusive, and replace $A_i$ with that integer.
Sort $A$ in ascending order.

Print the expected value of $A_K$ after the two operations, modulo $998244353$ .

How to print a number modulo $998244353$ ?

It can be proved that the sought expected value is always rational. Additionally, under the Constraints of this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$ , it can be proved that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$ . Print this $R$ .

Constraints

$1\leq K \leq N \leq 2000$
$1\leq M \leq 2000$
$0\leq A_i \leq M$
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $M$   $K$ 
 $A_1$   $A_2$   $\dots$   $A_N$

Output

Print the expected value of $A_K$ after the two operations, modulo $998244353$ .

Sample Input 1Copy

Copy

3 5 2
2 0 4

Sample Output 1Copy

Copy

In the operation 1, Snuke will replace $A_2$ with an integer between $1$ and $5$ . Let $x$ be this integer.

If $x=1$ or $2$ , we will have $A_2=2$ after the two operations.
If $x=3$ , we will have $A_2=3$ after the two operations.
If $x=4$ or $5$ , we will have $A_2=4$ after the two operations.

Thus, the expected value of $A_2$ is $\frac{2+2+3+4+4}{5}=3$ .

Sample Input 2Copy

Copy

2 3 1
0 0

Sample Output 2Copy

Copy

221832080

The expected value is $\frac{14}{9}$ .

Sample Input 3Copy

Copy

10 20 7
6 5 0 2 0 0 0 15 0 0

Sample Output 3Copy

Copy

617586310