Dãy đối xứng
Đề bài
Mô tả
Trong một kỳ thi cuối kỳ, thí sinh được yêu cầu giải một Thử thách Thú vị về Đếm Dãy Đối xứng (ICPC). Thử thách này yêu cầu đếm các dãy đối xứng chứa : các dãy không chỉ có tính đối xứng mà còn phải tuân theo một quy tắc quan trọng: tổng các phần tử của dãy phải bằng một giá trị cho trước.
Một dãy được gọi là dãy đối xứng nếu đọc từ trái sang phải giống như đọc từ phải sang trái. Cụ thể, dãy độ dài là dãy đối xứng nếu với mọi . Ví dụ, và là các dãy đối xứng, còn và thì không. Một dãy đối xứng được gọi là dãy đối xứng chứa nếu có ít nhất một phần tử của dãy bằng .
Cho hai số nguyên và , hãy đếm số dãy đối xứng chứa gồm các số nguyên dương có tổng các phần tử bằng . Hai dãy được coi là khác nhau nếu chúng có độ dài khác nhau hoặc khác nhau ở ít nhất một vị trí. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên (): số bộ test.
- Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (, ) mô tả một bộ test.
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng phần dư của kết quả khi chia cho .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 6 2 10 3 40 1 |
4 8 1037630 |
Ví dụ của đề gốc. Với , có dãy: , , , . |
| 4 1 1 3 2 5 1 4 3 |
1 0 3 0 |
Ví dụ bổ sung, tính bằng lời giải mẫu. Với , , các dãy đối xứng tổng là và , không dãy nào chứa . Với , có , , . |
Bình luận