Earthworms queue - MarisaOJ: Marisa Online Judge

Earthworms queue

Time limit: 3000 ms
Memory limit: 768 MB
There are $n$ earthworms, each with a length ranging from $1$ to $6$. The earthworms are arranged in a line, numbered from $1$ to $n$. The current arrangement divides the earthworms into $n$ groups, where each earthworm forms its own group. Each earthworm is positioned at both the end and the beginning of its group. There are $m$ queries of the following types: - `1 i j`: Merge the two groups containing earthworms $i$ and $j$. Specifically, earthworm $j$ will stand immediately behind earthworm $i$. It is guaranteed that earthworm $i$ is currently at the end of its group, and earthworm $j$ is at the beginning of its group. The order of the remaining earthworms stays the same. - `2 i`: Split the earthworms in the group of earthworm $i$ that are positioned behind $i$ into a new group. The order of the remaining earthworms stays the same. - `3 s k`: Given a string $s$ and a positive integer $k$, for each consecutive substring $t$ of length $k$ (there are $|s| - k + 1$ such substrings for a string of length $|s|$), calculate the product of all $f(t)$ modulo $998244353$. The definition of $f(t)$ is provided below. For a group of earthworms, define the $k$-backward-string of an earthworm as follows: starting from this earthworm, move from left to right to obtain exactly $k$ earthworms (including itself), treating the length of each earthworm as a digit to form a string of digits. If it's not possible to find exactly $k$ earthworms, the backward $k$-string of this earthworm does not exist. For example, if there are $3$ earthworms numbered $10, 22$, and $3$ in the same group in order from left to right, with lengths $4, 5, 6$, the $3$-backward-string of earthworm $10$ is 456. Earthworm $22$ does not have a $3$-backward-string, but its $2$-backward-string is 56, and its $1$-backward-string is 6. The function $f(t)$ is the count of earthworms with a $k$-backward-string exactly equal to $t$ in the current arrangement. ### Input - The first line contains two integers $n$ and $m$. - The second line contains $n$ integers representing the lengths of the earthworms, each with a length not exceeding $6$. - The next $m$ lines represent the queries in one of the formats mentioned above. ### Output - For queries of type $3$, output an integer, which is the answer to the query. ### Example 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: - The positions of the earthworms after $4$ type $1$ operations: + `1 1 3` - `1 | 3 | 2 | 4 | 5`. + `1 2 5` - `1 3 | 2 | 5 4`. + `1 3 2` - `1 3 2 | 5 4`. + `1 5 4` - `1 3 2 5 4`. Input 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 ``` Output 2: ``` 64 1 0 75497471 1 0 75497471 ``` ### Constraints In each test case: - $n \le 2 \times 10^5, m \le 5 \times 10^5, k \le 50$ - $\sum{|s|} \le 10^7$ - For $c$ being the number of type $2$ queries, $c \le 10^3$ - If the column "All are $1$" is "Yes," then the lengths of the earthworms are $1$, and the string $s$ consists only of the digit $1$.
Test $n$ $m$ $k$ $\sum |s|$ $c$ All are $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}$