Cho một dãy gồm n số nguyên dương. Mỗi vị trí được chọn nhiều nhất một lần, và hai cách chọn khác nhau nếu chúng khác nhau ở ít nhất một vị trí. Hãy đếm số tập con có tổng đúng bằng x.
Input
Dòng đầu chứa hai số nguyên n và x.
Dòng thứ hai chứa n số nguyên dương a1,a2,…,an.
Output
In một số nguyên: số tập con theo chỉ số có tổng bằng x.
Constraints
1≤n≤40.
1≤x≤109.
1≤ai≤109.
Scoring
Subtask 1 (50% số điểm): n≤20.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
4 6
1 2 3 3
Output
3
Giải thích: Có một cách chọn cả hai phần tử mang giá trị 3, và hai cách chọn 1,2 cùng một trong hai phần tử đó, nên có tất cả 3 tập con.
Lời giải tóm tắt
Phân tích: Vét cạn trực tiếp có 2^n trạng thái, quá lớn khi n=40. Chia dãy thành hai nửa giúp mỗi phía chỉ có nhiều nhất 2^20 tổng tập con. Một tập con toàn cục tương ứng duy nhất với một tổng bên trái và một tổng bên phải.
Thuật toán: Liệt kê mọi tổng tập con của hai nửa, luôn gồm tổng 0. Sắp xếp danh sách tổng bên phải. Với mỗi tổng s bên trái, dùng equal_range để đếm số tổng bên phải bằng x-s rồi cộng vào đáp án 64 bit.
Chứng minh: Mỗi tập con của dãy tách duy nhất thành phần nằm ở nửa trái và phần nằm ở nửa phải. Nó có tổng x khi và chỉ khi hai tổng con thỏa s_L+s_R=x; thuật toán đếm đúng mọi cặp như vậy bằng equal_range. Tính duy nhất của phép tách bảo đảm không bỏ sót và không đếm lặp.
Độ phức tạp: Có O(2^{n/2}) trạng thái mỗi nửa. Thời gian O(2^{n/2} log 2^{n/2}), bộ nhớ O(2^{n/2}).