← 返回题目列表

AtCoder · abc295_e

H. 第 K 个数字

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个长度为 N 由之间的整数组成 0 和 M,包括: A=(A_1,A_2,\dots,A_N).

Snuke 将按顺序执行以下操作 1 和 2。

  1. 对于每个 i 这样 A_i=0,独立选择一个均匀随机整数 1 和 M,包含在内,并替换 A_i 与该整数。
  2. 排序 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将取代 A_2 之间的整数 1 和 5。让 x 是这个整数。

  • If x=1 or 2,我们将有 A_2=2 两次操作后。
  • If x=3,我们将有 A_2=3 两次操作后。
  • If x=4 or 5,我们将有 A_2=4 两次操作后。

因此,预期值 A_2 is \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