G - D. D. Construction 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

問題文

整数 N と N \times N 行列 A が与えられます。 以下の条件を満たす整数 M と M 個の N\times N 行列 B_1 , \ldots , B_M を出力してください。

  • 1 \leq M \leq 1000
  • 任意の 1\leq i \leq M について、B_i の全ての成分は絶対値が 40 以下の整数
  • 任意の 1 \leq i \leq M について、 \det(B_i) = \det(A)
  • \sum_{i=1}^{M} B_i = \text{diag}(MA_{11} , MA_{22} , \ldots , MA_{NN})

入力の条件下で、上記の制約を満たす出力が可能であることが証明できます。

\det の定義
行列 A に対し、 \det(A) は A の行列式を表します。

行列式のWikipediaへのリンク
\text{diag} の定義
N 個の整数 x_1, \cdots , x_N に対して、 \text{diag}(x_1 , x_2 , \ldots , x_N) は、
  • 1\leq i \leq N に対し、 i 行 i 列目の成分が x_i
  • 1\leq i , j \leq N, i\neq j に対し、 i 行 j 列目の成分が 0
となる N\times N 行列を表します。
対角行列のwikipediaへのリンク

制約

  • 入力は全て整数である。
  • 2\leq N \leq 8
  • |A_{ij}| \leq 40

入力

入力は以下の形式で標準入力から与えられる。

N
A_{11} \ldots A_{1N}
\vdots
A_{N1} \ldots A_{NN}

出力

1 行目に行列の個数 M を出力せよ。 続く NM 行のうち、 1 \leq i \leq M , 1 \leq j \leq N を満たす i , j に対して、 (i - 1)N + j 行目に B_i の j 行目を空白区切りで出力せよ。具体的には以下の形式で出力せよ。

M
(B_1)_{11} \ldots (B_1)_{1N}
\vdots
(B_1)_{N1} \ldots (B_1)_{NN}
\vdots
(B_M)_{11} \ldots (B_M)_{1N}
\vdots
(B_M)_{N1} \ldots (B_M)_{NN}
ただし、出力は問題文中の条件を満たす必要がある。 条件を満たす解が複数存在する場合は、どれを出力してもよい。

入力例1

3
1 0 0
0 1 0
0 0 1

出力例1

3
-2 -1 2
0 1 1
1 0 -2
0 0 -1
-1 2 -2
0 1 1
5 1 -1
1 0 1
-1 -1 4

出力された行列は、 \begin{pmatrix} -2&-1&2 \\ 0&1&1 \\ 1&0&-2 \end{pmatrix} と \begin{pmatrix} 0&0&-1 \\ -1&2&-2 \\ 0&1&1 \end{pmatrix} と \begin{pmatrix} 5&1&-1 \\ 1&0&1 \\ -1&-1&4 \end{pmatrix} の 3 つであり、

いずれも行列式は 1 = \det(A) で、これらの行列の和は、 \begin{pmatrix} 3&0&0 \\ 0&3&0 \\ 0&0&3 \end{pmatrix} になります。

これは、 \text{diag}(3,3,3) = \begin{pmatrix} 3&0&0 \\ 0&3&0 \\ 0&0&3 \end{pmatrix} に等しいです。