問題一覧 > 通常問題

No.2428 Returning Shuffle

レベル : / AI推定難易度 : 1375 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 106
作問者 : Kirby0717 / テスター : 0214sh7 noya2 👑 potato167 tassei903 ramdos ponjuice
お気に入りにしたユーザー ProblemId : 10012 / 自分の提出
問題文最終更新日: 2023-08-18 21:39:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
traP 作問ハッカソンコンテスト 001 (順位表) の他の問題:

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.
It is known that after performing this operation some number of times, $P$ returns to $(1,2,\cdots,N)$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。