A7068 | 美丽数组
时间限制2s
内存限制128MB
通过 / 提交0/0
题目描述
定义数组 $b_1,b_2,\ldots,b_n$（$n1$）的美丽值为
$\min\limits_{1 \le i j \le n} |b_i-b_j|$。
现在给定数组 $a_1,a_2,\ldots,a_n$ 和整数 $k$，请计算：所有长度恰好为 $k$ 的子序列的美丽值之和。
由于答案可能很大，请对 $998244353$ 取模输出。
一个序列 $x$ 是序列 $y$ 的子序列，当且仅当 $x$ 可以通过从 $y$ 中删除若干元素得到（保持剩余元素相对顺序不变）。
$\min\limits_{1 \le i j \le n} |b_i-b_j|$。
现在给定数组 $a_1,a_2,\ldots,a_n$ 和整数 $k$，请计算：所有长度恰好为 $k$ 的子序列的美丽值之和。
由于答案可能很大，请对 $998244353$ 取模输出。
一个序列 $x$ 是序列 $y$ 的子序列，当且仅当 $x$ 可以通过从 $y$ 中删除若干元素得到（保持剩余元素相对顺序不变）。
输入格式
第一行包含两个整数 $n,k$，满足 $2 \le k \le n \le 1000$。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $0 \le a_i \le 10^5$。
第二行包含 $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
样例解释 #1
输入：$n=4,k=3$，数组 $a=[1,7,3,5]$。
长度为 $3$ 的子序列一共有 $\binom{4}{3}=4$ 个：
- $[1,7,3]$：两两差为 $|1-7|=6,|1-3|=2,|7-3|=4$，美丽值为 $2$
- $[1,3,5]$：两两差为 $2,4,2$，美丽值为 $2$
- $[7,3,5]$：两两差为 $4,2,2$，美丽值为 $2$
- $[1,7,5]$：两两差为 $6,4,2$，美丽值为 $2$
样例解释 #2
输入：$n=5,k=5$，只能选整个数组 $[1,10,100,1000,10000]$ 这一种子序列。
相邻最小差出现在 $1$ 和 $10$ 之间，$|10-1|=9$，因此美丽值为 $9$，答案为 $9$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？