Đếm tập con
Đề bài
Mô tả
Cho dãy số nguyên . Hãy đếm số tập thỏa mãn đồng thời các điều kiện sau:
- ;
- ;
- .
Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho .
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test gồm hai dòng:
- Dòng đầu tiên chứa số nguyên ().
- Dòng thứ hai chứa số nguyên ().
Dữ liệu vào kết thúc bằng một dòng chứa duy nhất số (không phải một bộ test). Tổng các giá trị của mọi bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra kết quả trên một dòng.
Ràng buộc
- .
- (các có thể âm).
- Tổng các giá trị không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 2 3 3 2 3 1 0 |
0 6 |
Ở bộ test thứ nhất, với mọi tập , mọi đều có , nên không tập nào thỏa mãn. Ở bộ test thứ hai, có tập thỏa mãn: , , , , , . |
| 4 2 -1 1 3 0 |
15 | Ví dụ bổ sung (không có trong đề gốc). Mọi tập khác rỗng đều thỏa mãn: tập. |
Bình luận