#P3823. [NOI2017] 蚯蚓排队

[NOI2017] 蚯蚓排队

题目描述

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

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 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

提示

保证 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 i 的操作的次数,则 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