题目描述
对一个长度至少为 2 的序列 A=(a1,…,am),定义它的间距为不同下标对应元素之间的最小绝对差
D(A)=1≤i<j≤mmin∣ai−aj∣.
给定长度为 n 的序列 B=(b1,…,bn) 和整数 k。对每一种选出 k 个下标的方案,按原顺序取出这些位置的元素形成子序列,计算其间距。即使两个子序列的值序列相同,只要所选下标不同,就分别计入。求所有间距之和对 998244353 取模的结果。
输入格式
第一行两个整数 n,k。第二行 n 个整数 b1,…,bn。
输出格式
输出一个整数,表示间距之和对 998244353 取模后的结果。
样例 1
4 3
1 7 3 5
8
样例 2
5 5
1 10 100 1000 10000
9
原 PDF 间距公式的内层下标误印为 j=i 起,按两个样例,应从 j=i+1 起。原题另在下发文件中提供样例 3–5。
数据范围
2≤k≤n≤103,0≤bi≤105。
| 测试点 |
n 上界 |
k 上界 |
bi 上界 |
附加性质 |
| 1–2 |
8 |
105 |
|
| 3–4 |
30 |
| 5 |
100 |
| 6 |
150 |
| 7–8 |
200 |
| 9 |
103 |
103 |
3 |
| 10–11 |
100 |
| 12–13 |
105 |
bi=i |
| 14–15 |
5 |
|
| 16–20 |
103 |
原 PDF 题面