← 返回题目列表

AtCoder · tupc2022_f

F. 块旋转

中文机器翻译题面 查看原题

配点 : 300 点

問題文

N \times N 方格。 i = 1,2,\dots,N ,从左起: i 列从下方开始有 M_i 的 您可以创建一个包含 1 \times 1 个正方形的方块,每个方块都被涂上了颜色。这里, M_1,M_2,\dots,M_N 是单调非增的。从左边开始,第 i 列从下方数第 j 个方块被涂上了颜色 C_{i,j} 。

对于方格,考虑以下操作:

  • 将方格顺时针瞬间旋转 90^\circ 次,然后令有颜色的方块按照重力同时下落。更正式地说,对于左起第 i 列从下方数第 j 个方块,如果在与该方块同一高度、该方块右侧有 c_{i,j} 个方块,则将该方块移动到左起第 j 列从下方数第 c_{i,j}+1 个方格。此移动将同时对所有方块进行。

要使网格恢复到最初的布局,至少需要多少次操作呢? 998244353 求除以后的余数。

网格布局一致性的定义 对网格布局, N \times N 行列 A 进行对应。 A_{i,j} \, (i,j=1,2,\dots,N) 通过以下方式来确定。
  • 从网格的左边开始 i 列从下方数第 j 如果在第 x 个格子中存在方块,则为其颜色;如果不存在,则为…… 0
2 两个网格布局一致是指各自对应的矩阵一致。 A 由此得出,两者对应的矩阵一致即布局一致。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq \displaystyle \sum_{i=1}^N M_i \leq 10^5
  • N \geq M_1 \geq M_2 \geq \dots \geq M_N \geq 0
  • 1 \leq C_{i,j} \leq 10^5
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
M_1 C_{1,1} C_{1,2} \dots C_{1,M_1}
M_2 C_{2,1} C_{2,2} \dots C_{2,M_2}
\vdots
M_N C_{N,1} C_{N,2} \dots C_{N,M_N}

出力

答案 请打印除以 998244353 除以的余数。


入力例 1

2
2 1 2
1 3

出力例 1

3

通过操作,颜色的布局将如下变化。在这个例子中, 3 几次操作后可以恢复到原来的状态。


入力例 2

2
2 1 1
1 1

出力例 2

1

入力例 3

3
3 1 2 3
1 4
0

出力例 3

6

入力例 4

5
5 1 2 3 4 5
4 6 7 7 9
3 10 7 12
2 13 14
0

出力例 4

22