Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 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} となる.