← 返回题目列表

AtCoder · xmascon21_d

D. 行列式?

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

配点 : 100 点

去年的题目,沉迷于矩阵行列式问题的兔子,有一次竟然把矩阵的元素换成了矩阵......

問題文

由整数构成的 N 的 您可以创建一个包含 K \times K 行列 A_1, \ldots, A_N 。A_h 可以得到第 (i, j) 成分是 A_{h,i,j} (1 \le h \le N,1 \le i \le K,1 \le j \le K).

\mathfrak{S}_N 该值应乘以 N 阶对称群。K \times K 行列 \sum_{\sigma\in\mathfrak{S}_N} \operatorname{sgn}(\sigma) A_{\sigma(1)} \cdots A_{\sigma(N)} 的各个元素为 998244353 除以后的余数 (0 以上 998244353 以下)。

(也就是说,对于A_1, \ldots, A_N 的重新排列 N! 种情况,将该顺序的矩阵乘积乘以排列符号并相加的结果中,各个元素为 998244353 求被除以的余数。

制約

  • 1 \le N \le 32.
  • 1 \le K \le 8.
  • 0 \le A_{h,i,j} < 998244353 (1 \le h \le N,1 \le i \le K,1 \le j \le K).

入力

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

N K
A_{1,1,1} \cdots A_{1,1,K}
\vdots
A_{1,K,1} \cdots A_{1,K,K}
\vdots
\vdots
\vdots
A_{N,1,1} \cdots A_{N,1,K}
\vdots
A_{N,K,1} \cdots A_{N,K,K}

出力

求和的 (i, j) 成分 998244353 后的余数 b_{i,j} 作为(1 \le i \le K,1 \le j \le K),请以以下格式输出。

b_{1,1} \cdots b_{1,K}
\vdots
b_{K,1} \cdots b_{K,K}

入力例 1

2 3
2 7 1
8 2 8
1 8 2
8 4 5
9 0 4
5 2 3

出力例 1

31 998244259 998244344
100 998244306 55
61 998244298 16

A_1 A_2 - A_2 A_1 = \begin{bmatrix} 31 & -94 & -9 \\ 100 & -47 & 55 \\ 61 & -55 & 16 \end{bmatrix} 变为。


入力例 2

3 2
30 10
40 10
50 90
20 60
50 30
50 80

出力例 2

155000 122000
67000 364000

A_1 A_2 A_3 - A_1 A_3 A_2 - A_2 A_1 A_3 + A_2 A_3 A_1 + A_3 A_1 A_2 - A_3 A_2 A_1 = \begin{bmatrix} 155000 & 122000 \\ 67000 & 364000 \end{bmatrix} 变为。