Needle of Words
Xem PDFCho đa thức \(f = \sum_{i=0}^{n} a_i x^i\) trên \(\mathbb{Z}_p\), \(p = 998244353\). Định nghĩa \(s_k\) như sau:
Xử lý \(q\) truy vấn online: mỗi tham số số nguyên \(v\) trong truy vấn được giải mã thành \(v \oplus\) last_ans, với last_ans khởi đầu bằng 0 và cập nhật sau mỗi truy vấn Q. Có bốn loại truy vấn:
D — Thay \(f(x) \leftarrow \dfrac{f(x) - a_0}{x}\), tức là \(a_i \leftarrow a_{i+1}\) với mọi \(i \geq 0\).
S c — Thay \(f(x) \leftarrow f(x + c')\) với \(c' = c \oplus\) last_ans.
M m \(b_0 \ldots b_{m-1}\) — Thay \(f \leftarrow f \cdot g\) với \(g = \sum_{i=0}^{m-1} b_i x^i\) (các \(b_i\) không được mã hóa).
Q t — In ra \(s_{t'}\) với \(t' = t \oplus\) last_ans. Gán last_ans \(\leftarrow s_{t'}\).
Input
- Dòng đầu: hai số nguyên \(n\) và \(q\).
- Dòng hai: \(n+1\) số nguyên \(a_0, a_1, \ldots, a_n\).
- \(q\) dòng tiếp theo: mỗi dòng là một truy vấn theo định dạng trên.
Ràng buộc: \(1 \leq n \leq 2^{18}\), \(1 \leq q \leq 10^5\), \(0 \leq a_i, b_i, c < p\), \(m \leq 2^{17}\).
Output
Với mỗi truy vấn Q, in một số nguyên trên một dòng.
Example
Test
Input
3 6
0 0 1 0
M 3 1 0 1
Q 0
S 1
Q 0
D
Q 0Output
0
2
8Note
Ban đầu \(f = x^2\).
M 3 1 0 1: \(g = 1 + x^2\), \(f \leftarrow x^2(1+x^2) = x^2 + x^4\), tức \(a = [0,0,1,0,1,0]\).
Q 0: \(t' = 0 \oplus 0 = 0\), \(s_0 = 0! \cdot 0 = 0\). In \(0\). last_ans \(= 0\).
S 1: \(c' = 1 \oplus 0 = 1\), \(f \leftarrow f(x+1) = (x+1)^2 + (x+1)^4 = 2 + 6x + 7x^2 + 4x^3 + x^4\), tức \(a = [2,6,7,4,1,0]\).
Q 0: \(t' = 0 \oplus 0 = 0\), \(s_0 = 0! \cdot 2 = 2\). In \(2\). last_ans \(= 2\).
D: \(f \leftarrow \frac{f - 2}{x}\), \(a = [6,7,4,1,0]\).
Q 0: \(t' = 0 \oplus 2 = 2\), \(s_2 = 2! \cdot 4 = 8\). In \(8\). last_ans \(= 8\).
Scoring
- Subtask 1 : \(n, q \leq 1000\); không có truy vấn
M. - Subtask 2 : \(n \leq 2^{18}\), \(q \leq 500\); không có truy vấn
M. - Subtask 3 : Đủ 4 loại truy vấn; \(q \leq 200\).
- Subtask 4 : Không có ràng buộc bổ sung.
Bình luận