Tổng trong tập con
Cho dãy số có \(n\) phần tử: \(a_1, a_2, .., a_n\) và số nguyên \(m\), số nguyên dương \(S\); bạn hãy đếm xem có bao nhiêu cách chọn ra một dãy con có \(m\) phần tử mà không có hai phần tử nào nằm liên tiếp trong dãy ban đầu, đồng thời tổng các phần tử trong dãy con đã chọn không vượt quá \(S\).
Đầu vào
Dòng đầu tiên chứa số nguyên ba số nguyên \(n\), \(m\) và \(S\) \((1 \le 2*m \le n \le 50, -10^{12} \le S \le 10^{12})\).
Dòng tiếp theo chứa \(n\) số nguyên có giá trị tuyệt đối không vượt quá \(10^{12}\), các phần tử trong dãy số.
Ghi chú: Bạn hãy dùng kiểu số nguyên \(64\)bit để nhập dữ liệu.
Đầu ra
Một số tự nhiên duy nhất là kết quả bài toán, lấy số dư khi chia cho \(10^9 + 7\).
Subtask
\(30\%\) số test có \(n \le 40\).
Ví dụ
Đầu vào 1:
5 2 10
1 2 4 8 16Đầu ra 1:
3Giải thích: Các dãy con thỏa mãn đề bài là \((1, 4), (1, 8), (2, 8)\).
Đầu vào 2:
6 3 6
1 1 2 2 3 3Đầu ra 2:
4Giải thích: Các dãy con thỏa mãn đề bài là: \((1, 2, 3)\) (\(4\) dãy như vậy).
Comments
Bài này làm kiểu gì thế mn?
Bạn sử dụng kĩ thuật meet-in-the-middle: chia dãy số ban đầu ra hai dãy con các số liên tiếp đồ dài như nhau, giải cho từng dãy con rồi ghép lại đếm kết quả.
Tks. AC!