#2303. 「NOI2017」蚯蚓排队

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

题目描述

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

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

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

  1. 给出 iijj ,令 ii 号蚯蚓与 jj 号蚯蚓所在的两个队伍合并为一个队伍,具体来说,令 jj 号蚯蚓紧挨在 ii 号蚯蚓之后,其余蚯蚓保持队伍的前后关系不变。

  2. 给出 ii ,令 ii 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍,具体来说,在分离之后, ii 号蚯蚓在其中一个队伍的队尾,原本紧挨其后的那一只蚯蚓在另一个队伍的队首,其余蚯蚓保持队伍的前后关系不变。

  3. 给出一个正整数 kk 和一个长度至少为 kk 的数字串 ss ,对于 ss 的每个长度为 kk 的连续子串 tt (这样的子串共有 sk+1|s|-k+1 个,其中 s|s|ss 的长度),定义函数 f(t)f(t) ,询问所有这些f(t)f(t)乘积998244353998244353 取模后的结果。其中f(t)f(t)的定义如下:

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

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

输入格式

从标准输入读入数据。

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

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

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

  • 1 ii jj1i,jn1 \leq i, j \leq n)表示:令 ii 号与 jj 号蚯蚓所在的两个队伍合并为一个队伍,新队伍中, jj 号蚯蚓紧挨在 ii 号蚯蚓之后。保证在此操作之前, ii 号蚯蚓在某个队伍的队尾, jj 号蚯蚓在某个队伍的队首,且两只蚯蚓不在同一个队伍中。

  • 2 ii1in1 \leq i \leq n)表示:令 ii 号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前, ii 号蚯蚓不是某个队伍的队尾。

  • 3 ss kkkk为正整数,ss为一个长度至少为kk的数字串)表示:询问 ss 的每个长度为 kk 的子串 ttf(t)f(t) 的乘积,对998244353取模的结果。 f(t)f(t) 的定义见题目描述。

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

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

输出格式

输出到标准输出。

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

样例

样例 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(f(33)×f() \times f(33)×f() \times f(31)×f() \times f(13)×f() \times f(35)=0×0×0×0×0=0) = 0 \times 0 \times 0 \times 0 \times 0 = 0

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

接下来进行了若干次队伍的合并操作,使得所有蚯蚓合并成了一个队伍,这个队伍从前到后的蚯蚓依次为: 11 号蚯蚓(长度为 33 )、33 号蚯蚓(长度为 33 )、22 号蚯蚓(长度为 11 )、55 号蚯蚓(长度为 33 )、44 号蚯蚓(长度为 55 )。

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

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

第五次询问: 44 号蚯蚓、 55号蚯蚓没有向后3数字串,而其他蚯蚓都有。得到的3个向后3数字串135331313,答案为 f(f(333)×f() \times f(331)×f() \times f(313)×f() \times f(135)=0×1×1×1=0) = 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

解释

对于第四次、第七次询问,输入的 ss 为 30 个字符6,所有 f(t)f(t) 的乘积是 230=10737418242^{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个测试点。

数据范围与提示

保证 n2×105n \leq 2 \times 10^{5}m5×105m \leq 5 \times 10^{5}k50k \leq 50

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

cc 为某个输入文件中形如2 ii的操作的次数,则 c103c \leq 10^{3}

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

测试点编号 nn mm kk s\sum |s| cc 全为1\texttt{1}
1 =1=1 103\leq 10^{3} =1=1 103\leq 10^{3} =0=0 No
2 20\leq 20 40\leq 40 10\leq 10
3 150\leq 150 2,000\leq 2,000 50\leq 50 103\leq 10^{3}
4 500\leq 500 600\leq 600 =0=0
5 103\leq 10^{3} 2,000\leq 2,000 103\leq 10^{3}
6 5×104\leq 5 \times 10^{4} 6×104\leq 6 \times 10^{4} 5\leq 5 5×104\leq 5 \times 10^{4}
7 50\leq 50 =0=0 Yes
8 No
9 103\leq 10^{3}
10 8×104\leq 8 \times 10^{4} 2.5×106\leq 2.5 \times 10^{6} =0=0
11 103\leq 10^{3}
12 105\leq 10^{5} 1.1×105\leq 1.1 \times 10^{5} 6\leq 6 105\leq 10^{5}
13 50\leq 50 =0=0 Yes
14 No
15 103\leq 10^{3}
16 1.5×105\leq 1.5 \times 10^{5} 5×106\leq 5 \times 10^{6} =0=0
17 103\leq 10^{3}
18 2×105\leq 2 \times 10^{5} 5×105\leq 5 \times 10^{5} =1=1 107\leq 10^{7} =0=0
19 103\leq 10^{3}
20 2.5×105\leq 2.5 \times 10^{5} 7\leq 7 2×105\leq 2 \times 10^{5}
21 50\leq 50 =0=0 Yes
22 No
23 103\leq 10^{3}
24 3×105\leq 3 \times 10^{5} 107\leq 10^{7} =0=0
25 103\leq 10^{3}

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