Bạn được cho 1 xâu a gồm n ký tự chỉ gồm các ký tự như &
, |
, ^
(tương đương với phép toán AND, OR, XOR). Bạn phải thực hiện q truy vấn:
- 1 k x: Cập nhật ký tự thứ k trong xâu a thành x (1\le k\le n, x thuộc 1 trong 3 loại ký tự như trên)
- 2 l r k u v: Tính độ đẹp của xâu trong đoạn [l,r] với các giá trị k,u,v (1\le l\le r\le n,1\le k\le 20,0\le u\le v<2^k)
a độ dài x với các giá trị k,u,v như sau: Là số lượng dãy b thỏa mãn (0\le b_i<2^k):
định nghĩa độ đẹp của một xâu ký tựChú ý: Thứ tự thực hiện tính toán theo các ký tự của xâu a được thực hiện từ trái sang phải
VD: Xâu |^
với k=1,u=1,v=1 thì có các khả năng như sau:
0|0^0=0
0|0^1=1
0|1^0=1
0|1^1=0
1|0^0=1
1|0^1=0
1|1^0=1
1|1^1=0
Theo như kết quả ở trên, có 4 kết quả thỏa mãn. Vậy độ đẹp của xâu |^
với k=1,u=1,v=1 là 4
Nhiệm vụ của bạn là phải tính toán các kết quả của truy vấn 2. Vì kết quả rất lớn nên hãy xuất kết quả mod\ 10^9+7
Input, Output và Subtasks
Input: (AOXQUERIES.inp
)
- Dòng đầu tiên gồm 2 số n và q (1\leq n,q\leq 5\cdot 10^3)
- Dòng thứ hai gồm duy nhất một xâu a
- Sau đó là q dòng, mỗi dòng nhập truy vấn như trên
Output: (AOXQUERIES.out
)
- Với mỗi truy vấn loại 2, xuất ra kết quả cần tìm
Subtasks
- Subtask 1 (5\%): n,q\le 20, k=1 với mọi truy vấn loại 2.
- Subtask 2 (10\%): n,q\le 20.
- Subtask 3 (10\%): u=0,v=2^k-1 với mọi truy vấn loại 2.
- Subtask 4 (10\%): k=1 với mọi truy vấn loại 2.
- Subtask 5 (15\%): u=v với mọi truy vấn loại 2.
- Subtask 6 (50\%): Không có ràng buộc gì thêm
Sample
Input (AOXQUERIES.inp
)
3 4
&|^
2 2 3 1 1 1
1 3 |
2 2 3 1 0 1
2 1 3 2 2 2
Output (AOXQUERIES.out
)
4
8
39
Note
Trong truy vấn 1 đã giải thích ở trên nên sẽ không giải thích lại.
Trong truy vấn 2 dễ dàng nhận thấy với mọi dãy b kết quả có thể ra trong khoảng [0,1], mà có 8 dãy b có thể tạo nên xuất ra 8
Bình luận