201393: [AtCoder]ARC139 D - Priority Queue 2

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $700$ points

Problem Statement

You are given a multiset of integers with $N$ elements: $A=\lbrace A_1,A_2,...,A_N \rbrace$. It is guaranteed that every element of $A$ is between $1$ and $M$ (inclusive).

Let us repeat the following operation $K$ times.

  • Choose an integer between $1$ and $M$ (inclusive) and add it to $A$. Then, delete the $X$-th smallest value in $A$.

Here, the $X$-th smallest value in $A$ is the $X$-th value from the front in the sequence of the elements of $A$ sorted in non-decreasing order.

There are $M^K$ ways to choose an integer $K$ times between $1$ and $M$. Assume that, for each of these ways, we have found the sum of the elements of $A$ after the operations with the corresponding choices. Find the sum, modulo $998244353$, of the $M^K$ values computed.

Constraints

  • $1 \le N,M,K \le 2000$
  • $1 \le X \le N+1$
  • $1 \le A_i \le M$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $K$ $X$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer.


Sample Input 1

2 4 2 1
1 3

Sample Output 1

99

We start with $A=\{1,3\}$. Here is an example of how we do the operations.

  • Add $4$ to $A$, making $A=\{1,3,4\}$. Then, delete the $1$-st smallest value, making $A=\{3,4\}$.

  • Add $3$ to $A$, making $A=\{3,3,4\}$. Then, delete the $1$-st smallest value, making $A=\{3,4\}$.

In this case, the sum of the elements of $A$ after the operations is $3+4=7$.


Sample Input 2

5 9 6 3
3 7 1 9 9

Sample Output 2

15411789

Input

题意翻译

给定 $n,m,k,x$,给定了一个有 $n$ 个元素的可重集合 $a_i\in [1,m]$,会进行 $k$ 次如下操作:选择一个数 $y\in[1,m]$ 加到 $a$ 中,并把 $a$ 中第 $x$ 小的元素删除。 有 $m^k$ 种情况,对于每种情况的价值定义为最后 $a$ 集合的和,对于所有情况价值求和。 - $1\le n,m,k\le 2000$,$1\le x\le n+1$,$1\le a_i\le m$

加入题单

上一题 下一题 算法标签: