通过：0，提交：0，通过率：0%

关于密码箱的近10条评论(全部评论)

3603. [NOI 2021]密码箱

★★★★ 输入文件：code.in 输出文件：code.out 简单对比
时间限制：2 s 内存限制：1024 MiB

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

1.初始时数列长度为2且有$a_0=0,a_1=1$；

2.对数列依次进行若干次操作，其中每次操作是以下两种类型之一：

·W 类型：给数列的最后一项加1。

·E 类型：若数列的最后一项为1，则给倒数第二项加1；否则先给数列的最后一项减1，接着在数列尾再加两项，两项的值都是 1。

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

$$f(a_0,\cdots,a_{k-1},a_k)=\begin{cases}a_0, & k=0\\f(a_0,a_1,\cdots,a_{k-2},a_{k-1}+\frac{1}{a_k},& k\geq 1\end{cases}$$

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

·APPEND c，在现有操作序列后追加一次 c 类型操作，其中 c 为字符 W 或 E。

·FLIP l r，反转现有操作序列中第$l$个至第$r$个（下标从1开始，修改包含端点$l$和$r$，下同）操作，即所有 W 变为 E，所有 E 变为 W。

·REVERSE l r，翻转现有操作序列中第$l$个至第$r$个操作，也就是将这个区间中的操作逆序。

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

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

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

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

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

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3

样例2与测试数据1$\sim$4满足同样的约束条件。

样例3与测试数据5$\sim$7满足同样的约束条件。

样例4与测试数据8$\sim$10满足同样的约束条件。

样例5与测试数据15$\sim$20满足同样的约束条件。

对于所有测试点：$1\leq n\leq 10^5,1\leq q\leq 10^5$。

对于 APPEND 修改，保证给出的 c 为大写英文字母 W 或 E。

对于 FLIP 和 REVERSE 修改，保证$1\leq l\leq r\leq L$，其中$L$是当前操作序列的长度。

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

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

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

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

NOI2021 Day2 Task2