Kth Number

题目描述

我们有一个长度为 $N$ 的序列，元素为介于 $0$ 和 $M$（包含两端）之间的整数：$A=(A_1,A_2,\dots,A_N)$。 Snuke 将按顺序执行下列操作 1 和 2。

对于每个满足 $A_i=0$ 的 $i$，独立地从 $1$ 到 $M$（包含两端）均匀随机选择一个整数，并用该整数替换 $A_i$。 将 $A$ 按升序排序。

输出在这两步操作之后 $A_K$ 的期望值，对 $998244353$ 取模。

如何对 $998244353$ 取模输出一个数？

可以证明所求的期望值总是有理数。 此外，在本题的约束下，当该值用互素的两个整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时，可以证明存在唯一的整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。输出这个 $R$。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出在这两步操作之后 $A_K$ 的期望值，对 $998244353$ 取模。

3 5 2
2 0 4

3

2 3 1
0 0

221832080

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

617586310

提示

$1\leq K \leq N \leq 2000$ $1\leq M \leq 2000$ $0\leq A_i \leq M$ 输入中的所有数值均为整数。在操作 1 中，Snuke 会把 $A_2$ 替换为 $1$ 到 $5$ 之间的某个整数。设该整数为 $x$。

如果 $x=1$ 或 $2$，在两步操作之后我们会有 $A_2=2$。 如果 $x=3$，我们会有 $A_2=3$。 如果 $x=4$ 或 $5$，我们会有 $A_2=4$。

因此，$A_2$ 的期望值为 $\frac{2+2+3+4+4}{5}=3$.
期望值为 $\frac{14}{9}$.

标签: AtCoder|abc295E

来源

AtCoder|abc295E