← 返回题目列表

Codeforces · 1188/C

C. 阵美

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

我们称数组为美 $$$b_1, b_2, \ldots, b_n$$$ ($$$n > 1$$$)  — $$$\min\limits_{1 \leq i < j \leq n} |b_i - b_j|$$$。

给你一个数组 $$$a_1, a_2, \ldots a_n$$$ 和一个数字 $$$k$$$。计算长度恰好为 $$$k$$$ 的数组的所有子序列的美度总和。由于这个数字可能非常大,因此输出它对 $$$998244353$$$ 取模。

如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是数组 $$$b$$$ 的子序列。

输入

第一行包含整数 $$$n, k$$$ ($$$2 \le k \le n \le 1000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^5$$$)。

输出

输出一个整数——长度恰好为 $$$k$$$ 的数组的所有子序列的美度总和。由于这个数字可能非常大,因此输出它对 $$$998244353$$$ 取模。

示例

输入 #1

4 3
1 7 3 5

输出 #1

8

输入 #2

5 5
1 10 100 1000 10000

输出 #2

9

注意

第一个例子中有 $$$4$$$ 长度为 $$$3$$$ — $$$[1, 7, 3]$$$, $$$[1, 3, 5]$$$, $$$[7, 3, 5]$$$, $$$[1, 7, 5]$$$ 的子序列,每个子序列都有美丽 $$$2$$$,所以答案是$$$8$$$。

在第二个示例中,只有一个长度为 $$$5$$$ 的子序列 — 整个数组,其美感等于 $$$|10-1| = 9$$$。