| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 4 | 0 | 0 | 0.000% |
There are $n$ worms numbered from 1ドル$ to $n$. The length of a worm can be represented by a positive integer between 1ドル$ and 6ドル$. You want to arrange the worms into several queues. Initially, each worm is in its own queue with only one worm (itself). Each worm is both at the front and at the end of its queue.
There are $m$ operations. Each operation is one of the following three types:
1 i j where 1ドル \leq i,j \leq n$: Merge the queue worm $i$ is in with the queue worm $j$ is in. In the new queue, worm $j$ will be immediately after worm $i$ (and for the rest of the worms, the worm before/after them remains unchanged). It is guaranteed that worm $i$ is at the tail of some queue , worm $j$ is at the front of some queue, and $i,j$ are not in the same queue.2 i where 1ドル \leq i \leq n$: Split the queue between worm $i$ and the worm immediately after $i$. It is guaranteed that worm $i$ is not at the tail of some queue.3 s k where $k$ is a positive integer and $s$ is a numeric string with length at least $k$: Find the product of $f(t)$ modulo 998ドル,244円,353円$ where $t$ is over all substrings of length $k$ in $s$. There are $|s| - k + 1$ such substrings $t$ given $s$ and $k$.The definition of $f(t)$ is given below.
For a given queue, the $k$-string after worm $i$ is obtained by starting from worm $i,ドル walking towards the tail of the queue, and finding the $k$ nearest worms to $i,ドル including $i,ドル and concatenating the lengths of these worms. If there are fewer than $k$ worms before reaching the tail, then worm $i$ won't have a $k$-string. For example, if the numbers of worms in a queue are 10,22,3ドル$ and they have lengths 4,5,6ドル$; then the 3-string after worm 10ドル$ is 456ドル,ドル worm 22ドル$ does not have a 3-string, but its 2-string is 56ドル$ and its 1-string is 5ドル$.
$f(t)$ denotes the number of worms whose $k$-string is exactly $t$.
The first line consists of two positive integers $n,m$ denoting the number of worms and the number of operations.
In the second line, there are $n$ positive integers not exceeding 6ドル$ denoting the length of worm 1,ドル\ldots,n$.
In the following $m$ lines, each line specifies an operation.
The input file might be large.
For each operation 3 s k, output a line with an integer denoting the output.
$n \leq 2 \times 10^5, m \leq 5 \times 10^5, k \leq 50$.
Let $\sum |s|$ denote the sum of lengths of $s$ in all queries. $\sum |s| \leq 10^7$.
Let $c$ denote the number of operations of the form 2 i, then $c \leq 10^3$.
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
For the first query, since there is only one worm in each queue, no worms have a 2-string, so the output is simply 0ドル$.
For the second query, each worm's 1-string is the string formed by the worm's own length, so we see the 1-strings are 1,3,3,3,5ドル$ (in no particular order) and the output is $f(3) \cdot f(3) \cdot f(3) \cdot f(1) \cdot f(3) \cdot f(5) = 81$.
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
For the 4th and the 7th query, since $s$ is 30ドル$ 6s, $f(t)$ is $f(t) = 2^{30}$. Output it modulo 998ドル,244円,353円$.