Cho N độ cao đôi một khác nhau. Bạn được sắp xếp chúng theo một hoán vị f1,f2,…,fN. Chi phí của hoán vị là
∣f1−f2∣+∣f2−f3∣+⋯+∣fN−1−fN∣.
Hãy đếm số hoán vị có chi phí không vượt L.
Input
Dòng đầu chứa N và L.
Dòng thứ hai chứa N số nguyên A1,A2,…,AN.
Output
In số hoán vị có chi phí không vượt L modulo 109+7.
Constraints
1≤N≤100.
1≤L≤1000.
1≤Ai≤1000 và các Ai đôi một khác nhau.
Scoring
Subtask 1 (50% số điểm): N≤8.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
3 2
1 2 3
Output
2
Giải thích: Chỉ hai thứ tự đơn điệu (1,2,3) và (3,2,1) có tổng chênh lệch bằng 2. Bốn hoán vị còn lại đều có chi phí lớn hơn 2.
Lời giải tóm tắt
Ý tưởng: Sắp xếp các độ cao tăng dần rồi chèn chúng vào skeleton của hoán vị cuối. Dùng trạng thái (c,cost,e), trong đó c là số thành phần, e∈{0,1,2} là số đầu toàn cục đã được chiếm.
Ý tưởng: Khi tăng độ cao thêm gap, có 2c-e đầu hở nên chi phí bắt buộc tăng (2c-e)*gap. Độ cao mới có thể tạo thành phần ở khoảng trong, chiếm một đầu toàn cục, nối vào một đầu hở, hoặc gộp hai thành phần. Các hệ số là số vị trí tương ứng.
Ý tưởng: Mọi hoán vị có một quá trình chèn duy nhất; tổng chênh lệch được phân bổ chính xác qua các khoảng độ cao. Trạng thái cuối cần c=1,e=2 và cost≤L. Độ phức tạp O(N^2L), bộ nhớ O(NL).
Lỗi cần tránh: Tăng chi phí bằng 2·component·gap mà quên trừ các đầu toàn cục đã được chiếm.
Lỗi cần tránh: Giữ đúng mọi trường hợp biên và kiểu số đã nêu trong đề.
Lỗi cần tránh: Chỉ lấy modulo ở những bài có yêu cầu modulo; bài 10 và bài 9 phải giữ nguyên số nguyên 64 bit.