#P6446. 序列间距

    ID: 6413 传统题 3000ms 128MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高贡献法计数 DP前缀和优化 DP同向双指针滚动数组

序列间距

题目描述

对一个长度至少为 22 的序列 A=(a1,…,am)A=(a_1,\ldots,a_m),定义它的间距为不同下标对应元素之间的最小绝对差

D(A)=min⁡1≤i<j≤m∣ai−aj∣.D(A)=\min_{1\le i<j\le m}|a_i-a_j|.

给定长度为 nn 的序列 B=(b1,…,bn)B=(b_1,\ldots,b_n) 和整数 kk。对每一种选出 kk 个下标的方案,按原顺序取出这些位置的元素形成子序列,计算其间距。即使两个子序列的值序列相同,只要所选下标不同,就分别计入。求所有间距之和对 998244353998244353 取模的结果。

输入格式

第一行两个整数 n,kn,k。第二行 nn 个整数 b1,…,bnb_1,\ldots,b_n。

输出格式

输出一个整数,表示间距之和对 998244353998244353 取模后的结果。

样例 1

4 3
1 7 3 5
8

样例 2

5 5
1 10 100 1000 10000
9

原 PDF 间距公式的内层下标误印为 j=ij=i 起,按两个样例,应从 j=i+1j=i+1 起。原题另在下发文件中提供样例 3–5。

数据范围

2≤k≤n≤1032\le k\le n\le10^3,0≤bi≤1050\le b_i\le10^5。

测试点 nn 上界 kk 上界 bib_i 上界 附加性质
1–2 8 10510^5
3–4 30
5 100
6 150
7–8 200
9 10310^3 10310^3 3
10–11 100
12–13 10510^5 bi=ib_i=i
14–15 5
16–20 10310^3

原 PDF 题面