AT_abc295_e [ABC295E] Kth Number

题目描述

有一个长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$，其中每个元素都是 $0$ 到 $M$ 之间的整数。

现在，すぬけくん将依次进行以下两个操作：

1. 对于所有满足 $A_i=0$ 的 $i$，独立且等概率地选择一个 $1$ 到 $M$ 之间的整数，将 $A_i$ 替换为该整数。
2. 将数列 $A$ 按升序排序。

请输出すぬけくん完成操作 1 和 2 后 $A_K$ 的期望值，结果对 $998244353$ 取模。

“对 $998244353$ 取模输出期望值” 的意思是：可以证明，所求期望值一定是有理数。在本题的约束下，设其为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 互质。则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出すぬけくん完成操作 1 和 2 后 $A_K$ 的期望值，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3 5 2
2 0 4

输出 #1

3

输入输出样例 #2

输入 #2

2 3 1
0 0

输出 #2

221832080

输入输出样例 #3

输入 #3

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

输出 #3

617586310

说明/提示

约束

• $1\leq K\leq N\leq 2000$
• $1\leq M\leq 2000$
• $0\leq A_i\leq M$
• 输入均为整数

样例解释 1

すぬけくん在操作 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$。

样例解释 2

期望值为 $\frac{14}{9}$。

由 ChatGPT 4.1 翻译