A7062. 小组项目分组
编程题
省选/NOI-
知识点
题目描述
班里有 $n$ 个学生，第 $i$ 个学生单独完成自己那部分需要 $a_i$ 分钟。
学生们要被分成若干个小组（允许一个人单独成组）。对一个小组，定义它的不平衡度为该组内最大的 $a$ 减去最小的 $a$；如果小组只有一个人，不平衡度为 $0$。
所有小组的不平衡度之和不超过 $k$。问一共有多少种不同的分组方式？
如果存在一对学生，在一种分组中属于同一组，在另一种分组中属于不同组，则这两种分组方式视为不同。
学生们要被分成若干个小组（允许一个人单独成组）。对一个小组，定义它的不平衡度为该组内最大的 $a$ 减去最小的 $a$；如果小组只有一个人，不平衡度为 $0$。
所有小组的不平衡度之和不超过 $k$。问一共有多少种不同的分组方式？
如果存在一对学生，在一种分组中属于同一组，在另一种分组中属于不同组，则这两种分组方式视为不同。
输入格式
第一行包含两个整数 $n,k$。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。
输出格式
输出一个整数，表示方案数对 $10^9+7$ 取模后的结果。
输入输出样例
输入 #1
3 2 2 4 5
输出 #1
3
输入 #2
4 3 7 8 9 10
输出 #2
13
输入 #3
4 0 5 10 20 21
输出 #3
1
说明/提示
## 数据范围
- $1 \le n \le 200$
- $0 \le k \le 1000$
- $1 \le a_i \le 500$
## 样例解释
- 样例 1：共有 3 种可行分组：
- $\{1,2\},\{3\}$，总不平衡度 $2+0=2$
- $\{1\},\{2,3\}$，总不平衡度 $0+1=1$
- $\{1\},\{2\},\{3\}$，总不平衡度 $0$
- 样例 3：要求总不平衡度为 $0$，只能所有人都单独成组，因此答案为 $1$。
- $1 \le n \le 200$
- $0 \le k \le 1000$
- $1 \le a_i \le 500$
## 样例解释
- 样例 1：共有 3 种可行分组：
- $\{1,2\},\{3\}$，总不平衡度 $2+0=2$
- $\{1\},\{2,3\}$，总不平衡度 $0+1=1$
- $\{1\},\{2\},\{3\}$，总不平衡度 $0$
- 样例 3：要求总不平衡度为 $0$，只能所有人都单独成组，因此答案为 $1$。