UOJ Logo Universal Online Judge

UOJ

#315. 【NOI2017】蚯蚓排队

统计

蚯蚓幼儿园有 $n$ 只蚯蚓。幼儿园园长神刀手为了管理方便,时常让这些蚯蚓们列队表演。

所有蚯蚓用从 $1$ 到 $n$ 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示,根据入园要求,所有蚯蚓的长度都不超过 $6$。神刀手希望这些蚯蚓排成若干个队伍,初始时,每只蚯蚓各自排成一个仅有一只蚯蚓的队伍,该蚯蚓既在队首,也在队尾。

神刀手将会依次进行 $m$ 次操作,每个操作都是以下三种操作中的一种:

  1. 给出 $i$ 和 $j$,令 $i$ 号蚯蚓与 $j$ 号蚯蚓所在的两个队伍合并为一个队伍,具体来说,令 $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后,其余蚯蚓保持队伍的前后关系不变。
  2. 给出 $i$,令 $i$ 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍,具体来说,在分离之后,$i$ 号蚯蚓在其中一个队伍的队尾,原本紧挨其后的那一只蚯蚓在另一个队伍的队首,其余蚯蚓保持队伍的前后关系不变。
  3. 给出一个正整数 $k$ 和一个长度至少为 $k$ 的数字串 $s$,对于 $s$ 的每个长度为 $k$ 的连续子串 $t$(这样的子串共有 $|s|-k+1$ 个,其中 $|s|$ 为 $s$ 的长度),定义函数 $f(t)$,询问所有这些 $f(t)$ 的乘积对 $998244353$ 取模后的结果。其中 $f(t)$ 的定义如下:

对于当前的蚯蚓队伍,定义某个蚯蚓的向后 $k$ 数字串为:从该蚯蚓出发,沿队伍的向后方向,寻找最近的 $k$ 只蚯蚓(包括其自身),将这些蚯蚓的长度视作字符连接而成的数字串;如果这样找到的蚯蚓不足 $k$ 只,则其没有向后 $k$ 数字串。例如蚯蚓的队伍为 $10$ 号蚯蚓在队首,其后是 $22$ 号蚯蚓,其后是 $3$ 号蚯蚓(为队尾),这些蚯蚓的长度分别为 $4$、$5$、$6$,则 $10$ 号蚯蚓的向后 $3$ 数字串456, $22$ 号蚯蚓没有向后 $3$ 数字串,但其向后 $2$ 数字串56,其向后 $1$ 数字串5

而 $f(t)$ 表示所有蚯蚓中,向后 $k$ 数字串恰好为 $t$ 的蚯蚓只数。

输入格式

从标准输入读入数据。

输入文件的第一行有两个正整数 $n,m$,分别表示蚯蚓的只数与操作次数。

第二行包含 $n$ 个不超过 $6$ 的正整数,依次表示编号为 $1,2,\dots,n$ 的蚯蚓的长度。

接下来 $m$ 行,每行表示一个操作。每个操作的格式可以为:

  • 1 i j($1 \leq i, j \leq n$)表示:令 $i$ 号与 $j$ 号蚯蚓所在的两个队伍合并为一个队伍,新队伍中, $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后。保证在此操作之前, $i$ 号蚯蚓在某个队伍的队尾, $j$ 号蚯蚓在某个队伍的队首,且两只蚯蚓不在同一个队伍中。
  • 2 i($1 \leq i \leq n$)表示:令 $i$ 号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前, $i$ 号蚯蚓不是某个队伍的队尾。
  • 3 s k($k$ 为正整数,$s$ 为一个长度至少为 $k$ 的数字串)表示:询问 $s$ 的每个长度为 $k$ 的子串 $t$ 的 $f(t)$ 的乘积,对 $998244353$ 取模的结果。 $f(t)$ 的定义见题目描述。

同一行输入的相邻两个元素之间,用恰好一个空格隔开。

输入文件可能较大,请不要使用过于缓慢的读入方式。

输出格式

输出到标准输出。

依次对于每个形如 3 s k 的操作,输出一行,仅包含一个整数,表示询问的结果。

样例一

input

5 9
3 1 3 5 3
3 333135 2
3 333135 1
1 1 3
1 2 5
1 3 2
1 5 4
3 333135 2
3 333135 1
3 333135 3

output

0
81
1
81
0

explanation

第一次询问:由于每个队伍均只有一只蚯蚓,所以没有任何蚯蚓有向后 $2$ 数字串,答案为 $f(\mathtt{33}) \times f(\mathtt{33}) \times f(\mathtt{31}) \times f(\mathtt{13}) \times f(\mathtt{35}) = 0 \times 0 \times 0 \times 0 \times 0 = 0$ 。

第二次询问:每个队伍仍只有一只蚯蚓,每只蚯蚓的向后 $1$ 数字串就是将自己的长度视为字符的数字串,即:得到的 $5$ 个向后 $1$ 数字串13335(不分先后顺序,下同),答案为 $f(\mathtt{3}) \times f(\mathtt{3}) \times f(\mathtt{3}) \times f(\mathtt{1}) \times f(\mathtt{3}) \times f(\mathtt{5}) = 3 \times 3 \times 3 \times 1 \times 3 \times 1 = 81$ 。

接下来进行了若干次队伍的合并操作,使得所有蚯蚓合并成了一个队伍,这个队伍从前到后的蚯蚓依次为: $1$ 号蚯蚓(长度为 $3$ )、$3$ 号蚯蚓(长度为 $3$ )、$2$ 号蚯蚓(长度为 $1$ )、$5$ 号蚯蚓(长度为 $3$ )、$4$ 号蚯蚓(长度为 $5$ )。

第三次询问: $4$ 号蚯蚓没有向后 $2$ 数字串,而其他蚯蚓都有。得到的 $4$ 个向后 $2$ 数字串13313335,答案为 $f(\mathtt{33}) \times f(\mathtt{33}) \times f(\mathtt{31}) \times f(\mathtt{13}) \times f(\mathtt{35}) = 1 \times 1 \times 1 \times 1 \times 1 = 1$。

第四次询问:虽然队伍的排列方式改变了,但是每只蚯蚓的向后 $1$ 数字串没有发生改变,所以答案同第二次询问。

第五次询问: $4$ 号蚯蚓、$5$ 号蚯蚓没有向后 $3$ 数字串,而其他蚯蚓都有。得到的 $3$ 个向后 $3$ 数字串135331313,答案为 $f(\mathtt{333}) \times f(\mathtt{331}) \times f(\mathtt{313}) \times f(\mathtt{135}) = 0 \times 1 \times 1 \times 1 = 0$。

样例二

input

2 10
6 6
3 666666 1
1 1 2
3 666666 2
3 666666 4
3 666666666666666666666666666666 1
2 1
1 2 1
3 666666 2
3 666666 4
3 666666666666666666666666666666 1

output

64
1
0
75497471
1
0
75497471

explanation

对于第四次、第七次询问,输入的 $s$ 为 30 个字符 6,所有 $f(t)$ 的乘积是 $2^{30} = 1073741824$,输出的结果是这个数对于 $998244353$ 取模的结果。

样例三

见样例数据下载。

该组样例的数据范围同第 5 个测试点。

样例四

见样例数据下载。

该组样例的数据范围同第 10 个测试点。

样例五

见样例数据下载。

该组样例的数据范围同第 15 个测试点。

样例六

见样例数据下载。

该组样例的数据范围同第 20 个测试点。

限制与约定

保证 $n \leq 2 \times 10^{5}$,$m \leq 5 \times 10^{5}$,$k \leq 50$ 。

设 $\sum |s|$ 为某个输入文件中所有询问的 $s$ 的长度总和,则 $\sum |s| \leq 10^{7}$ 。

设 $c$ 为某个输入文件中形如 2 i 的操作的次数,则 $c \leq 10^{3}$ 。

每个测试点的详细信息见下表:

测试点编号$n$$m$$k$$\sum |s|$$c$全为 1
1$=1$$\leq 10^{3}$$=1$$\leq 10^{3}$$=0$No
2$\leq 20$$\leq 40$$\leq 10$
3$\leq 150$$\leq 2,000$$\leq 50$$\leq 10^{3}$
4$\leq 500$$\leq 600$$=0$
5$\leq 10^{3}$$\leq 2,000$$\leq 10^{3}$
6$\leq 5 \times 10^{4}$$\leq 6 \times 10^{4}$$\leq 5$$\leq 5 \times 10^{4}$
7$\leq 50$$=0$Yes
8No
9$\leq 10^{3}$
10$\leq 8 \times 10^{4}$$\leq 2.5 \times 10^{6}$$=0$
11$\leq 10^{3}$
12$\leq 10^{5}$$\leq 1.1 \times 10^{5}$$\leq 6$$\leq 10^{5}$
13$\leq 50$$=0$Yes
14No
15$\leq 10^{3}$
16$\leq 1.5 \times 10^{5}$$\leq 5 \times 10^{6}$$=0$
17$\leq 10^{3}$
18$\leq 2 \times 10^{5}$$\leq 5 \times 10^{5}$$=1$$\leq 10^{7}$$=0$
19$\leq 10^{3}$
20$\leq 2.5 \times 10^{5}$$\leq 7$$\leq 2 \times 10^{5}$
21$\leq 50$$=0$Yes
22No
23$\leq 10^{3}$
24$\leq 3 \times 10^{5}$$\leq 10^{7}$$=0$
25$\leq 10^{3}$

如果一个测试点的 “全为 1” 的一列为 “Yes”,表示该测试点的所有蚯蚓的长度均为 $1$,并且所有询问串 $s$ 的每一位也均为 1

时间限制:$2\texttt{s}$

空间限制:$1\texttt{GB}$

下载

样例数据下载