102954: [Atcoder]ABC295 E - Kth Number
Description
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 1
3 5 2 2 0 4
Sample Output 1
3
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 2
2 3 1 0 0
Sample Output 2
221832080
The expected value is $\frac{14}{9}$.
Sample Input 3
10 20 7 6 5 0 2 0 0 0 15 0 0
Sample Output 3
617586310
Input
题意翻译
给定长度为 $n$ 的数列 $a$ 与 $m$，$k$。接下来，$a$ 中所有为 $0$ 的数将被等概率地替换为 $[1,m]$ 中的任意一个整数。接着将数列 $a$ 从小到大排序。请你求出 $a_k$ 的期望值，结果对 $998244353$ 取模。 $1\le k\le n\le2000$，$1\le m\le 2000$。Output
问题描述
我们有一个长度为 N 的序列，其中包含 0 到 M（含）之间的整数：$A=(A_1,A_2,\dots,A_N)$。
Snuke 将按以下顺序执行操作 1 和 2。
- 对于每个 $i$ 使得 $A_i=0$，独立地在 1 到 M（含）之间选择一个均匀随机整数，并用该整数替换 $A_i$。
- 将 $A$ 按升序排序。
输出执行两次操作后 $A_K$ 的期望值，对 998244353 取模。
如何打印一个对 998244353 取模的数？
可以证明，所求期望值总是有理数。 此外，在本问题的约束下，当该值表示为 $\frac{P}{Q}$ 时，其中 $P$ 和 $Q$ 是互质的整数，可以证明存在一个唯一的整数 $R$，使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。输出这个 $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$
输出
输出执行两次操作后 $A_K$ 的期望值，对 998244353 取模。
样例输入 1
3 5 2 2 0 4
样例输出 1
3
在操作 1 中，Snuke 将用一个在 1 到 5 之间的整数替换 $A_2$。令 $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$。
样例输入 2
2 3 1 0 0
样例输出 2
221832080
期望值为 $\frac{14}{9}$。
样例输入 3
10 20 7 6 5 0 2 0 0 0 15 0 0
样例输出 3
617586310