#P6343. 分组问题

    ID: 6418 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-差分转化线性 DP计数 DP滚动数组

分组问题

题目描述

有 nn 名学生,第 ii 名学生完成一个课时需要 sis_i 单位时间。将所有学生分成若干非空组,每人恰好属于一组。

一组的不和谐度为该组最大 sis_i 减去最小 sis_i,单人组的不和谐度为 00。求所有组的不和谐度之和不超过 kk 的分组方案数,对 109+710^9+7 取模。

学生按编号区分。小组没有编号。如果存在两名学生在一种方案中同组、另一种方案中不同组,则两种方案不同。

输入格式

第一行两个整数 n,kn,k。第二行 nn 个整数 s1,…,sns_1,\ldots,s_n。

输出格式

输出一行一个整数,表示答案对 109+710^9+7 取模后的结果。

样例

4 5
1 3 5 7
9

原题另在下发文件中提供样例 2、3。

数据范围

1≤n≤5001\le n\le500,0≤k≤10000\le k\le1000。原 PDF 标注 1≤si≤5001\le s_i\le500,本站现有评测中的 sis_i 实际范围为 0≤si≤9000\le s_i\le900。

子任务 分值 附加性质
1 20 n≤10n\le10
2 15 k≤2k\le2
3 sis_i 只有两种不同取值
4 20 ∑isi≤1000\sum_i s_i\le1000
5 30 无

原 PDF 题面