#2303. 「NOI2017」蚯蚓排队

内存限制:2048 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

蚯蚓幼儿园有 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 的操作,输出一行,仅包含一个整数,表示询问的结果。

样例

样例 1

输入

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

输出

0
81
1
81
0

解释

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

第二次询问:每个队伍仍只有一只蚯蚓,每只蚯蚓的向后1数字串就是将自己的长度视为字符的数字串,即:得到的5个向后1数字串13335(不分先后顺序,下同),答案为 f( 3 ) \times f( 3 ) \times f( 3 ) \times f( 1 ) \times f( 3 ) \times f( 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( 33 ) \times f( 33 ) \times f( 31 ) \times f( 13 ) \times f( 35 ) = 1 \times 1 \times 1 \times 1 \times 1 = 1

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

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

样例 2

输入

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

输出

64
1
0
75497471
1
0
75497471

解释

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

样例3

见附加文件下的 ex_3.inex_3.ans

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

样例4

见附加文件下的 ex_4.inex_4.ans

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

样例5

见附加文件下的 ex_5.inex_5.ans

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

样例6

见附加文件下的 ex_6.inex_6.ans

该组样例的数据范围同第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 全为 \texttt{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
8 No
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
14 No
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
22 No
23 \leq 10^{3}
24 \leq 3 \times 10^{5} \leq 10^{7} =0
25 \leq 10^{3}

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