No.2428 Returning Shuffle
タグ : / 解いたユーザー数 101
作問者 :
Kirby0717
/ テスター :
0214sh7
noya2
👑 
potato167
tassei903
ramdos
ponjuice
問題文
長さ $N$ の数列 $P$ と$M$ 個の巡回置換 $(S_{1,1}\ \cdots\ S_{1,T_1}),\cdots,(S_{M,1}\ \cdots\ S_{M,T_M})$があります。
はじめ、 $P = (1,2,\cdots,N)$ です。
あなたは今から以下の操作を $1$ 回以上行います。
- $P$ に対し $M$ 個の巡回置換を順番に適用する
$P$ を $(1,2,\cdots,N)$ に戻すためには操作を最小で何回行う必要がありますか？
$\bmod 998244353$ で出力してください。
巡回置換 $(S_1\ \cdots\ S_K)$ を数列 $A$ に適用するとは、
$S_{K+1}$ を $S_1$ とした時、 $n=1,2,\dots ,K$ について数列 $A$ の左から $S_n$ 番目の要素で $S_{n+1}$ 番目の要素を同時に置き換える操作の事です。サンプル1の説明も参考にしてください。
制約
- $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)$
- 入力は全て整数
入力
$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}$
操作 $1$ 回は、 $M$ 個の巡回置換 $(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})$ を左から順に $P$ に適用する事です。
出力
答えを出力してください。
サンプル
サンプル1
入力
5 1 3 3 2 4
出力
3
適用する巡回置換は $(3\ 2\ 4)$ であり、これを $P$ に適用すると $(1,2,3,4,5)\rightarrow (1,3,4,2,5)\rightarrow (1,4,2,3,5)\rightarrow (1,2,3,4,5) $ となり、 $3$ 回で元に戻ります。
サンプル2
入力
3 3 2 1 2 2 3 1 3 2 1 3
出力
1
$P = (1,2,3)$ に巡回置換 $(1\ 2)$ を適用すると $P = (2,1,3)$ となり、次に $(3\ 1)$ を適用すると $P = (3,1,2)$ となり最後に $(2\ 1\ 3)$ を適用することで $P = (1,2,3)$ となることから、この操作は恒等置換であることがわかります。このため $1$ 回の操作で $P$ がもとに戻るといえます。
サンプル3
入力
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
出力
12
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。