Gán nhị phân
Đề bài
Mô tả
Vương là một trong những nhà toán học vĩ đại nhất mọi thời đại! Sở thích của anh là tìm ra các tính chất toán học của mọi thứ, đôi khi của cả những thứ không tồn tại! Vào ngày sinh nhật, người bạn lập trình viên tặng anh một xâu nhị phân độ dài . Sau một lúc, anh tìm ra hai tính chất rất thú vị của :
- : độ dài của xâu ngắn nhất không phải là dãy con của .
- : số xâu độ dài không phải là dãy con của .
Thấy Vương thích thú tìm ra hai tính chất này, người bạn lập trình viên nghĩ rằng sẽ thật tuyệt nếu thay đổi xâu một chút. Anh lần lượt thực hiện thao tác thay đổi xâu . Mỗi thao tác thuộc một trong các loại sau:
0 l r: gán bằng .1 l r: gán bằng .F l r: lật , tức là với mọi , nếu bằng thì đổi thành , ngược lại đổi thành .
Và tất nhiên, với mỗi phiên bản đã thay đổi của , Vương cũng vui vẻ tìm và , vì hôm nay là sinh nhật anh!
Nhưng một câu đố thì không thể thiếu đáp án. Cho xâu và danh sách thao tác thay đổi, hãy giúp người bạn lập trình viên tìm và sau mỗi thao tác, để anh có thể đối chiếu với kết quả của Vương. Vì đáp án có thể rất lớn, hãy in theo modulo .
Xâu là dãy con của xâu nếu có thể nhận được từ bằng cách xóa đi một số (có thể không xóa, hoặc xóa hết) ký tự. Ví dụ, "bd", "acd", "b" là dãy con của "abcd", còn "da" thì không.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và () là độ dài xâu và số thao tác.
- Dòng thứ hai chứa xâu nhị phân độ dài .
- Dòng thứ trong dòng tiếp theo mô tả thao tác thứ ở một trong các dạng sau:
0 l r(): gán bằng .1 l r(): gán bằng .F l r(): lật .
Dữ liệu ra
Sau mỗi thao tác, in ra một dòng gồm hai số nguyên và modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 0110 0 2 3 1 3 4 F 2 3 |
1 1 2 1 3 4 |
Ban đầu (với , : các xâu , nhưng không cần in). Sau thao tác , : chỉ có xâu độ dài không là dãy con. Sau thao tác , : xâu là xâu duy nhất độ dài không là dãy con. Sau thao tác , : các xâu ngắn nhất không là dãy con là . |
| 2 4 01 F 1 2 F 1 1 0 2 2 1 1 2 |
2 3 1 1 1 1 1 1 |
Lần lượt (các xâu ), , , . Ví dụ bổ sung (không có trong đề gốc). |
Bình luận