← 返回题目列表

AtCoder · npcapc_2024_j

J. 再次排列问题

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

配点 : 100 点

問題文

(1,2,\dots,N) 的排列有 M 个。 第i 个排列是 P_i = (P_{i,1},P_{i,2},\dots,P_{i,N}) 。

你有一个数列 Q=(1,2,\dots,N) 。并且,你可以进行以下操作 0 次或更多次。

  • 1 \le i \le M 满足的整数 i ,选择并Q 在 (Q_{P_{i,1}},Q_{P_{i,2}},\dots,Q_{P_{i,N}}) 更新为。

操作后的 Q 所有可能的数列的逆序数总和 998244353 取余。起初,数列

制約

  • 1 \le N \le 30
  • 1 \le M \le 30
  • P_i=(P_{i,1},P_{i,2},\dots,P_{i,N}) 是 给出了 (1,2,\dots,N) 的排列

部分点

针对此问题设置了部分分数。 满足

  • N \le 6 满足的数据集中的正确答案情况 10 点。

入力

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

N M
P_{1,1} P_{1,2} \dots P_{1,N}
P_{2,1} P_{2,2} \dots P_{2,N}
\vdots
P_{M,1} P_{M,2} \dots P_{M,N}

出力

打印答案。


入力例 1

3 2
1 2 3
2 3 1

出力例 1

4

你能够得到的数列个数为 Q 是 给出了 (1,2,3),(2,3,1),(3,1,2) 的 3 个。每个的翻转数为 0,2,2 所以答案是 0 + 2 + 2 = 4 。


入力例 2

5 2
3 4 5 1 2
1 5 4 3 2

出力例 2

50

入力例 3

30 12
1 2 9 4 5 6 7 8 3 10 11 12 19 14 15 25 17 18 20 26 21 22 23 24 16 29 27 28 13 30
9 2 27 4 5 10 7 8 1 25 11 12 24 14 15 16 17 18 19 20 21 22 23 28 6 26 3 13 29 30
1 5 3 29 2 6 7 8 9 10 11 12 13 16 15 18 17 14 19 20 21 22 28 27 25 26 24 23 4 30
7 2 3 25 5 6 1 28 21 15 11 12 13 14 10 17 16 18 19 20 9 22 23 24 4 26 27 8 29 30
1 2 5 4 16 6 7 8 9 11 10 3 13 14 15 12 17 23 19 20 21 29 18 24 25 26 27 28 22 30
19 24 3 4 1 6 7 8 9 10 11 12 13 21 15 16 17 18 5 22 20 14 23 2 25 26 27 28 29 30
1 2 3 4 5 6 27 8 9 10 29 12 24 14 15 16 17 18 30 20 7 22 13 23 25 26 21 28 11 19
1 2 25 4 5 6 7 8 9 20 23 12 13 14 15 16 17 18 19 10 29 22 3 24 11 26 27 28 30 21
1 2 16 4 5 6 3 8 9 10 11 12 22 29 13 7 17 18 19 20 21 15 23 24 14 26 27 28 25 30
1 13 3 4 5 6 21 8 24 10 7 12 20 14 15 16 17 2 19 18 11 22 23 9 25 26 27 28 29 30
1 2 3 4 5 6 25 8 9 19 11 12 13 7 10 16 21 18 15 20 17 22 23 24 28 26 27 14 29 30
1 2 27 21 5 6 7 8 9 10 18 24 13 14 15 16 17 12 19 11 4 22 23 20 25 26 3 28 29 30

出力例 3

701414999