No.2428 Returning Shuffle
Problem Statement
There are a sequence $P$ of length $N$ and $M$ cyclic permutations $(S_{1,1}\ \cdots\ S_{1,T_1}),\cdots,(S_{M,1}\ \cdots\ S_{M,T_M})$.
Initially, $P = (1,2,\cdots,N)$.
You will now perform the following operation at least $1$ time.
- Apply the $M$ cyclic permutations to $P$ in order.
What is the minimum number of operations required to return $P$ to $(1,2,\cdots,N)$?
Output the answer $\bmod 998244353$.
Applying a cyclic permutation $(S_1\ \cdots\ S_K)$ to a sequence $A$ means the following operation:
letting $S_{K+1}$ be $S_1$, for $n=1,2,\dots ,K$, simultaneously replace, in the sequence $A$, the element that is $S_{n+1}$-th from the left with the element that is $S_n$-th from the left (the positions are written here in the reverse order of the original wording only for grammar). See also the explanation of Sample 1.
Constraints
- $2\le N\le 10^6$
- $1\le M\le 5\cdot 10^5$
- $2\le T_m\le N(1\le m\le M)$
- $1\le S_{m,t}\le N(1\le m\le M,1\le t\le T_m)$
- $S_{m,i}\neq S_{m,j}(1\le m\le M,1\le i,j\le T_m)$
- $2\le \sum\limits_{m=1}^M{T_m}\le 10^6(1\le m\le M)$
- All inputs are integers.
Input
$N\ M$
$T_1\ S_{1,1}\ S_{1,2}\ \cdots\ S_{1,T_1}$
$T_2\ S_{2,1}\ S_{2,2}\ \cdots\ S_{2,T_2}$
$\vdots$
$T_M\ S_{M,1}\ S_{M,2}\ \cdots\ S_{M,T_M}$
Performing the operation $1$ time means applying the $M$ cyclic permutations $(S_{1,1}\ S_{1,2}\ \cdots\ S_{1,T_1}),(S_{2,1}\ S_{2,2}\ \cdots\ S_{2,T_2}),\cdots,(S_{M,1}\ S_{M,2}\ \cdots\ S_{M,T_M})$ in order from left to right to $P$.
Output
Output the answer.
Sample
Sample 1
Input
5 1 3 3 2 4
Output
3
The cyclic permutation to apply is $(3\ 2\ 4)$, and applying it to $P$ gives $(1,2,3,4,5)\rightarrow (1,3,4,2,5)\rightarrow (1,4,2,3,5)\rightarrow (1,2,3,4,5) $, so it returns to the original after $3$ times.
Sample 2
Input
3 3 2 1 2 2 3 1 3 2 1 3
Output
1
Applying the cyclic permutation $(1\ 2)$ to $P = (1,2,3)$ gives $P = (2,1,3)$, next applying $(3\ 1)$ gives $P = (3,1,2)$, and finally applying $(2\ 1\ 3)$ gives $P = (1,2,3)$, so this operation is the identity permutation. Therefore, $1$ operation returns $P$ to the original.
Sample 3
Input
9 6 3 2 5 8 6 9 7 3 1 8 2 5 7 1 5 4 3 9 9 4 6 7 3 1 5 2 8 2 5 9 4 6 4 8 2
Output
12
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kirby0717
0214sh7
noya2