Đèn hoa đăng trên sông Hương
Đề bài
Mô tả
Trong dịp Festival Huế, một dãy gồm vị trí được chuẩn bị dọc bờ sông Hương. Các vị trí được đánh số từ đến từ trái sang phải. Mỗi vị trí hoặc có đúng một chiếc đèn hoa đăng, hoặc để trống, được mô tả bởi xâu độ dài : ký tự thứ của là 1 nếu vị trí có đèn, và là 0 nếu vị trí trống.
Dòng nước đẩy mỗi chiếc đèn đi đúng hai vị trí một lần. Một bước di chuyển đưa một chiếc đèn từ vị trí sang vị trí , với hoặc . Bước di chuyển chỉ được phép khi vị trí thuộc dãy, tức là , và khi cả vị trí lẫn vị trí nằm giữa và đều đang trống.
Mọi chiếc đèn trông giống hệt nhau, nên một cách sắp xếp chỉ được xác định bởi tập các vị trí có đèn. Có thể thực hiện bao nhiêu bước di chuyển cũng được, theo thứ tự bất kỳ.
Ban tổ chức kiểm tra đoạn của dãy. Với một đoạn được mô tả bởi hai số nguyên và , xét các vị trí cùng với các chiếc đèn mà các vị trí đó có lúc ban đầu, và coi chúng là một dãy riêng: trong khi kiểm tra đoạn này, đèn chỉ được di chuyển giữa các vị trí từ đến , phần còn lại của dòng sông được bỏ qua.
Với mỗi đoạn, hãy xác định có bao nhiêu cách sắp xếp khác nhau của đoạn đó có thể thu được. Cách sắp xếp ban đầu của đoạn cũng được tính. 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 và (, ): số vị trí và số đoạn cần kiểm tra.
- Dòng thứ hai chứa xâu độ dài , chỉ gồm các ký tự 0 và 1.
- Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (), mô tả một đoạn của dãy.
Dữ liệu ra
In ra dòng. Dòng thứ chứa số cách sắp xếp khác nhau có thể thu được trong đoạn thứ , lấy theo modulo .
Ràng buộc
- , .
- có độ dài và chỉ gồm các ký tự 0 và 1.
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 6 1001010 1 7 2 7 2 4 4 6 3 3 2 5 |
4 3 2 1 1 2 |
Ở đoạn thứ hai, các vị trí từ đến lúc đầu là 001010, và thu được đúng ba cách sắp xếp: 001010, 100010 và 101000. Ở đoạn thứ ba, các vị trí từ đến lúc đầu là 001, chiếc đèn có thể trôi sang trái hai vị trí, cho hai cách 001 và 100. Chiếc đèn này nằm ở vị trí của dòng sông nhưng ở vị trí thứ ba của đoạn, và chính vị trí trong đoạn quyết định nó đi được đến đâu. Ở đoạn thứ tư, các vị trí từ đến lúc đầu là 101 và không có bước di chuyển nào, vì mỗi chiếc đèn bị chiếc kia chặn. Ở đoạn thứ năm, vị trí không có đèn, nên cách sắp xếp rỗng là cách duy nhất. |
| 6 4 110011 1 6 2 5 3 6 1 1 |
5 3 3 1 |
Ví dụ bổ sung (không có trong đề gốc). Đoạn thứ nhất thu được 110011, 111001, 111100, 100111 và 001111. Đoạn thứ hai (1001) thu được 1001, 1100 và 0011. Đoạn thứ ba (0011) thu được 0011, 1001 và 1100. Đoạn thứ tư chỉ có một chiếc đèn ở vị trí duy nhất. |
Bình luận