P3823 [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 \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$ | $\leq 10^{3}$ | $=0$ | No | | 3 | $\leq 150$ | $\leq 2,000$ | $\leq 50$ | $\leq 10^{3}$ | $\leq 10^{3}$ | No | | 4 | $\leq 500$ | $\leq 600$ | $\leq 50$ | $\leq 10^{3}$ | $=0$ | No | | 5 | $\leq 10^{3}$ | $\leq 2,000$ | $\leq 50$ | $\leq 10^{3}$ | $\leq 10^{3}$ | No | | 6 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 5$ | $\leq 5 \times 10^{4}$ | $\leq 10^{3}$ | No | | 7 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 50$ | $\leq 5 \times 10^{4}$ | $=0$ | Yes | | 8 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 50$ | $\leq 5 \times 10^{4}$ | $=0$ | No | | 9 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 50$ | $\leq 5 \times 10^{4}$ | $\leq 10^{3}$ | No | | 10 | $\leq 5 \times 10^{4}$ | $\leq 8 \times 10^{4}$ | $\leq 50$ | $\leq 2.5 \times 10^{6}$ | $=0$ | No | | 11 | $\leq 5 \times 10^{4}$ | $\leq 8 \times 10^{4}$ | $\leq 50$ | $\leq 2.5 \times 10^{6}$ | $\leq 10^{3}$ | No | | 12 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 6$ | $\leq 10^{5}$ | $\leq 10^{3}$ | No | | 13 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 50$ | $\leq 10^{5}$ | $=0$ | Yes | | 14 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 50$ | $\leq 10^{5}$ | $=0$ | No | | 15 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 50$ | $\leq 10^{5}$ | $\leq 10^{3}$ | No | | 16 | $\leq 10^{5}$ | $\leq 1.5 \times 10^{5}$ | $\leq 50$ | $\leq 5 \times 10^{6}$ | $=0$ | No | | 17 | $\leq 10^{5}$ | $\leq 1.5 \times 10^{5}$ | $\leq 50$ | $\leq 5 \times 10^{6}$ | $\leq 10^{3}$ | No | | 18 | $\leq 2 \times 10^{5}$ | $\leq 5 \times 10^{5}$ | $=1$ | $\leq 10^{7}$ | $=0$ | No | | 19 | $\leq 2 \times 10^{5}$ | $\leq 5 \times 10^{5}$ | $=1$ | $\leq 10^{7}$ | $\leq 10^{3}$ | No | | 20 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 7$ | $\leq 2 \times 10^{5}$ | $\leq 10^{3}$ | No | | 21 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 50$ | $\leq 2 \times 10^{5}$ | $=0$ | Yes | | 22 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 50$ | $\leq 2 \times 10^{5}$ | $=0$ | No | | 23 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 50$ | $\leq 2 \times 10^{5}$ | $\leq 10^{3}$ | No | | 24 | $\leq 2 \times 10^{5}$ | $\leq 3 \times 10^{5}$ | $\leq 50$ | $\leq 10^{7}$ | $=0$ | No | | 25 | $\leq 2 \times 10^{5}$ | $\leq 3 \times 10^{5}$ | $\leq 50$ | $\leq 10^{7}$ | $\leq 10^{3}$ | No | 如果一个测试点的“全为`1`”的一列为“Yes”，表示该测试点的所有蚯蚓的长度均为 1，并且所有询问串 $s$ 的每一位也均为`1`。