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 $ .