#P7739. [NOI2021] 密码箱

[NOI2021] 密码箱

题目描述

Yelekastee 是 U 国著名的考古学家。在最近的一次考古行动中,他发掘出了一个远古时期的密码箱。经过周密而严谨的考证,Yelekastee 得知密码箱的密码和某一个数列 {an}\{ a_n \} 相关。数列 {an}\{ a_n \} 可以用如下方式构造出来:

  1. 初始时数列长度为 22 且有 a0=0,a1=1a_0 = 0, a_1 = 1
  2. 对数列依次进行若干次操作,其中每次操作是以下两种类型之一:
  • W 类型:给数列的最后一项11
  • E 类型:若数列的最后一项11,则给倒数第二项加 11;否则先给数列的最后一项11,接着在数列尾再加两项,两项的值都是 11

受到技术限制,密码箱并没有办法完整检查整个数列,因此密码箱的密码设定为数列 {an}\{ a_n \} 经过函数 ff 作用后的值,其中 ff 的定义如下:

$$f(a_0, \ldots , a_{k - 1}, a_k) = \begin{cases} a_0, & k = 0 \\ f \! \left( a_0, a_1, \ldots , a_{k - 2}, a_{k - 1} + \frac{1}{a_k} \right) \! , & k \ge 1 \end{cases} $$

Yelekastee 并不擅长运算,因此他找到了你,希望你能根据他提供的操作序列计算出密码箱的密码。不幸的是,他的记性并不是很好,因此他会随时对提供的操作序列做出一些修改,这些修改包括以下三种:

  • APPEND c,在现有操作序列后追加一次 c 类型操作,其中 c 为字符 WE
  • FLIP l r,反转现有操作序列中第 ll 个至第 rr 个(下标从 11 开始,修改包含端点 llrr,下同)操作,即所有 W 变为 E,所有 E 变为 W
  • REVERSE l r,翻转现有操作序列中第 ll 个至第 rr 个操作,也就是将这个区间中的操作逆序。

输入格式

输入第一行包含两个正整数 n,qn, q,分别表示初始的操作序列长度和修改的次数。

第二行包含一个长为 nn 且仅包含大写字母 WE 的字符串,表示初始操作序列。

接下来 qq 行,每行表示一次修改。每种修改的格式如【题目描述】所述。

输出格式

输出共 q+1q + 1 行,每行两个整数,其中第一行表示初始操作序列对应的密码,接下来 qq 行则分别输出每次修改之后的操作序列对应的密码。

容易发现密码一定是正有理数。若真实的密码为 ab\frac{a}{b},其中 a,b>0a, b > 0gcd(a,b)=1\gcd(a, b) = 1,则你需要在对应的行内顺次输出 aabb998244353998244353 后的余数。

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3

2 3
3 4
5 3
5 2

提示

【样例解释 #1】

操作序列 数列 {an}\{ a_n \} 密码
初始 WE (0,1,1,1)(0, 1, 1, 1) 23\frac{2}{3}
第一次修改后 WEE (0,1,2,1)(0, 1, 2, 1) 34\frac{3}{4}
第二次修改后 EWE (1,1,1,1)(1, 1, 1, 1) 53\frac{5}{3}
第三次修改后 EEW (2,2)(2, 2) 52\frac{5}{2}

【样例 #2】

见附件 code/code2.incode/code2.ans

该样例与测试数据 141 \sim 4 满足同样的约束条件。

【样例 #3】

见附件 code/code3.incode/code3.ans

该样例与测试数据 575 \sim 7 满足同样的约束条件。

【样例 #4】

见附件 code/code4.incode/code4.ans

该样例与测试数据 8108 \sim 10 满足同样的约束条件。

【样例 #5】

见附件 code/code5.incode/code5.ans

该样例与测试数据 152015 \sim 20 满足同样的约束条件。

【数据范围】

对于所有测试点:1n1051 \le n \le {10}^51q1051 \le q \le {10}^5

对于 APPEND 修改,保证给出的 c 为大写英文字母 WE

对于 FLIPREVERSE 修改,保证 1lrL1 \le l \le r \le L,其中 LL 是当前操作序列的长度。

请注意由于有 APPEND 操作,操作序列的长度最大可能有 2×1052 \times {10}^5

测试点编号 n,qn, q \le 特殊限制
141 \sim 4 20002000
575 \sim 7 105{10}^5 A
8108 \sim 10 B,C
111411 \sim 14 C
152015 \sim 20

特殊限制 A:保证在任意时刻操作序列中不会出现连续相同的两个字符。

特殊限制 B:保证没有 FLIP 修改。

特殊限制 C:保证没有 REVERSE 修改。