← 返回题单
题单练习 动态规划的优化
← 上一题 下一题 →

A7062 | 小组项目分组

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

班里有 $n$ 个学生，第 $i$ 个学生单独完成自己那部分需要 $a_i$ 分钟。

学生们要被分成若干个小组（允许一个人单独成组）。对一个小组，定义它的不平衡度为该组内最大的 $a$ 减去最小的 $a$；如果小组只有一个人，不平衡度为 $0$。

所有小组的不平衡度之和不超过 $k$。问一共有多少种不同的分组方式？

如果存在一对学生，在一种分组中属于同一组，在另一种分组中属于不同组，则这两种分组方式视为不同。

输入格式

第一行包含两个整数 $n,k$。
第二行包含 $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
C++ 编辑器
输入
输出