Bài tập nhóm

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Lớp học có $n$ học sinh đang làm bài tập nhóm. Các học sinh sẽ chia thành các nhóm (mỗi nhóm có thể gồm một hoặc nhiều học sinh), làm phần việc của mình một cách độc lập, rồi cùng thảo luận kết quả.

Học sinh thứ $i$ cần $a_{i}$ phút để hoàn thành phần việc của mình. Nếu trong cùng một nhóm có học sinh nhanh và học sinh chậm thì sẽ rất khó chịu — định nghĩa độ chênh của một nhóm là $max a_{i} - min a_{i}$ trên các học sinh thuộc nhóm đó. Một nhóm chỉ có một học sinh có độ chênh bằng $0$ .

Đếm số cách chia $n$ học sinh thành các nhóm sao cho tổng độ chênh của tất cả các nhóm không vượt quá $k$ . Hai cách chia được xem là khác nhau nếu tồn tại một cặp học sinh ở cùng nhóm trong cách chia này nhưng ở khác nhóm trong cách chia kia.

In kết quả theo modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

Một số nguyên duy nhất — số cách chia nhóm hợp lệ, lấy modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq n \leq 200$
$0 \leq k \leq 1000$
$1 \leq a_{i} \leq 500$

Ví dụ

Input	Output	Giải thích
3 2 2 4 5	3	Ba cách chia hợp lệ: {1,2},{3} (chênh $2 + 0 = 2$ ); {1},{2,3} (chênh $0 + 1 = 1$ ); {1},{2},{3} (chênh $0$ ).
4 3 7 8 9 10	13	Có $13$ cách chia với tổng độ chênh $\leq 3$ .
4 0 5 10 20 21	1	Tổng độ chênh phải bằng $0$ , nên mỗi học sinh phải tạo thành nhóm riêng.

Bình luận

Không có bình luận tại thời điểm này.