#NOI2021E. 密码箱

密码箱

题目描述

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(a0,,ak1,ak)={a0,k=0f(a0,,ak1+1ak),k1f(a_0,\cdots,a_{k−1},a_k)= \begin{cases} a_0,&k=0\\ f(a_0,\cdots,a_{k−1}+\frac{1}{a_k}),&k\geq 1 \end{cases}

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

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

输入格式

从文件 code.in 中读入数据。

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

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

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

输出格式

输出到文件 code.out 中。

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

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

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3
2 3
3 4
5 3
5 2

样例 1 解释

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

样例 2

见选手目录下的 code2.incode2.ans

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

样例 3

见选手目录下的 code3.incode3.ans

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

样例 4

见选手目录下的 code4.incode4.ans

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

样例 5

见选手目录下的 code5.incode5.ans

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

测试点约束

对于所有测试点:1n1051 \leq n \leq 10^50q1050 \leq q \leq 10^5

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

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

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

测试点编号 n,qn,q\leq 特殊限制
141\sim 4 20002000
575\sim 7 10510^5 AA
8108\sim 10 B,CB,C
111411\sim 14 CC
152015\sim 20

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

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

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