Nim
Đề bài
Mô tả
Alice và Bob chơi một biến thể của trò chơi Nim.
Để chuẩn bị, đầu tiên Bob chọn một dãy tăng ngặt gồm số nguyên . Sau đó, Alice xếp đống sỏi thành một hàng. Số sỏi trong mỗi đống phải là một số thuộc dãy của Bob. Các đống sỏi được phân biệt với nhau, nên có tổng cộng cấu hình ban đầu khác nhau.
Alice và Bob lần lượt thực hiện nước đi, Alice đi trước. Ở mỗi nước đi, người chơi phải chọn hoặc đống sỏi và bốc một số dương viên sỏi từ mỗi đống đã chọn. Được phép bốc số lượng khác nhau ở mỗi đống. Người không thể thực hiện nước đi hợp lệ sẽ thua.
Giả sử cả Alice và Bob đều chơi tối ưu, hãy đếm số cấu hình ban đầu mà Alice thua và Bob thắng. Vì đáp án có thể rất lớn, hãy in ra đáp án theo modulo .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên dương và : độ dài dãy của Bob và số đống sỏi (, ).
- Dòng thứ hai chứa số nguyên : dãy số của Bob ().
Dữ liệu ra
In ra đáp án, theo modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 1 2 |
2 | Có cấu hình. Alice thua ở đúng hai cấu hình và . |
| 9 123456789 1 2 3 4 5 6 7 8 9 |
552110917 |
Bình luận