UOJ Logo Universal Online Judge

UOJ

#677. 【NOI2021】密码箱

附件下载 统计

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

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

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

f(a0,,ak1,ak)={a0,k=0f(a0,a1,,ak2,ak1+1ak),k1

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

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

输入格式

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

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

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

输出格式

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

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

样例一

input

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3

output

2 3
3 4
5 3
5 2

explanation

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

样例二

见附加文件中的 ex_code2.inex_code2.ans

该样例与测试数据 14 满足同样的约束条件。

样例三

见附加文件中的 ex_code3.inex_code3.ans

该样例与测试数据 57 满足同样的约束条件。

样例四

见附加文件中的 ex_code4.inex_code4.ans

该样例与测试数据 810 满足同样的约束条件。

样例五

见附加文件中的 ex_code5.inex_code5.ans

该样例与测试数据 1520 满足同样的约束条件。

测试点约束

对于所有测试点:1n1051q105

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

对于 FLIPREVERSE 修改,保证 1lrL,其中 L 是当前操作序列的长度。

请注意由于有 APPEND 操作,操作序列的长度最大可能有 2×105

测试点编号 n,q 特殊限制
14 2000
57 105 A
810 105 B,C
1114 105 C
1520 105

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

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

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

时间限制:2s

空间限制:1GB