E - Kth Number
当前没有测试数据。
E - 第K个数
得分：500分
问题描述
我们有一个长度为$N$的序列，由介于$0$和$M$之间（包括$0$和$M$）的整数组成：$A=(A_1,A_2,\dots,A_N)$。
Snuke将按照以下两个步骤执行。
- 对于每个$A_i=0$的$i$，独立地选择介于$1$和$M$之间（包括$1$和$M$）的均匀随机整数，并用该整数替换$A_i$。
- 按升序对$A$排序。
输出两个操作后$A_K$的期望值，对$998244353$取模。
如何对数取模$998244353$?
可以证明，所求的期望值总是有理数。 另外，在此问题的限制下，当这个值表示为$\frac{P}{Q}$时，其中$P$和$Q$是互质的整数，可以证明存在唯一的整数$R$，使得$R \times Q \equiv P \pmod{998244353}$并且$0 \le R < 998244353$。输出这个$R$即可。约束
- $1\leq K \leq N \leq 2000$
- $1\leq M \leq 2000$
- $0\leq A_i \leq M$
- 输入中的所有值都是整数。
输入
从标准输入中，按以下格式给出：
输出
输出两个操作后$A_K$的期望值，对$998244353$取模。
3 5 2
2 0 4
3
在操作1中，Snuke将用介于$1$和$5$之间（包括$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 3 1
0 0
221832080
期望值为$\frac{14}{9}$。
10 20 7
6 5 0 2 0 0 0 15 0 0
617586310