Array Beauty

题意翻译

定义一个序列 $b_1, \ldots, b_n$ 的美丽值为 $\min_{1 \leq i < j \leq n}\{|b_i-b_j|\}$。给定一个长度为 $n$ 的序列 $a$，求 $a$ 的所有长度为 $k$ 的子序列的美丽值之和对 $998244353$ 取模的结果。 $2 \leq k \leq n \leq 1000$，$0 \leq a_i \leq 10^5$。

题目描述

Let's call beauty of an array $ b_1, b_2, \ldots, b_n $ ( $ n > 1 $ ) — $ \min\limits_{1 \leq i < j \leq n} |b_i - b_j| $ . You're given an array $ a_1, a_2, \ldots a_n $ and a number $ k $ . Calculate the sum of beauty over all subsequences of the array of length exactly $ k $ . As this number can be very large, output it modulo $ 998244353 $ . A sequence $ a $ is a subsequence of an array $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) elements.

输入输出格式

输入格式

The first line contains integers $ n, k $ ( $ 2 \le k \le n \le 1000 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^5 $ ).

输出格式

Output one integer — the sum of beauty over all subsequences of the array of length exactly $ k $ . As this number can be very large, output it modulo $ 998244353 $ .

输入输出样例

输入样例 #1

4 3
1 7 3 5

输出样例 #1

8

输入样例 #2

5 5
1 10 100 1000 10000

输出样例 #2

9

说明

In the first example, there are $ 4 $ subsequences of length $ 3 $ — $ [1, 7, 3] $ , $ [1, 3, 5] $ , $ [7, 3, 5] $ , $ [1, 7, 5] $ , each of which has beauty $ 2 $ , so answer is $ 8 $ . In the second example, there is only one subsequence of length $ 5 $ — the whole array, which has the beauty equal to $ |10-1| = 9 $ .