← 返回题目列表

AtCoder · arc139_d

D. 优先队列 2

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

分数: 700 点

问题陈述

给你一组整数 N 元素: A=\lbrace A_1,A_2,...,A_N \rbrace。保证每一个元素 A 介于 1 和 M (含)。

让我们重复以下操作 K 次。

  • 选择一个整数 1 和 M (含)并将其添加到 A。然后,删除 X- 第一个最小值 A.

这里, X- 第一个最小值 A 是 X- 元素序列中从前面算起的第一个值 A 按非降序排序。

有 M^K 选择整数的方法 K 次之间 1 和 M。假设对于每一种方式,我们都找到了元素的总和 A 后进行相应的操作选择。求总和,取模 998244353,其中 计算出 M^K 值。

约束

  • 1 \le N,M,K \le 2000
  • 1 \le X \le N+1
  • 1 \le A_i \le M
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M K X
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

2 4 2 1
1 3

示例输出 1

99

我们从 A=\{1,3\}。这是我们如何进行操作的示例。

  • 添加 4 to A, 制作 A=\{1,3,4\}。然后,删除 1-st 最小值,使得 A=\{3,4\}.

  • 添加 3 to A, 制作 A=\{3,3,4\}。然后,删除 1-st 最小值,使得 A=\{3,4\}.

在这种情况下,元素的总和 A 操作后是 3+4=7.


示例输入 2

5 9 6 3
3 7 1 9 9

示例输出 2

15411789