問題一覧 > 通常問題

No.2212 One XOR Matrix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 79
作問者 : ShirotsumeShirotsume / テスター : AngrySadEightAngrySadEight 👑 ygussanyygussany
10 ProblemId : 8773 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-04 12:42:34

問題文

$2^N \times 2^N$ のマス目があります。このマス目の各マスに $0$ 以上 $2^{2N}$ 未満の整数を $1$ つずつ書き込みます。このとき、$0$ 以上 $2^{2N}$ 未満の整数全てについて、その整数が書き込まれたマスがちょうど $1$ つ存在している必要があります。

すべての列について、列に含まれる要素の bitwise XOR が $1$ になり、かつ、すべての行について、行に含まれる要素の bitwise XOR が $1$ になるような書き込み方が存在するか判定し、存在するなら $1$ つ構築してください。

bitwise XOR とは(クリックで展開)

$2$ つの非負整数 $X, Y$ について、$X$ と $Y$ の bitwise XOR $X \oplus Y$ は以下のように定義されます。

  • $X \oplus Y$ を $2$ 進表記したときの $2^k$ $(k \geq 0)$ の位は、$X$ の $2$ 進表記での $2^k$ の位と、 $Y$ の $2$ 進表記での $2^k$ の位のうちちょうど一方が $1$ である場合 $1$ 、そうでない場合 $0$

例えば、 $3 \oplus 5 = 6, 1 \oplus 1 = 0$ です。

一般に $k$ 個の非負整数 $p_1, p_2, \dots, p_k$ の bitwise XOR は $( \dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots) \oplus p_k)$ と定義され、これは $p_1, p_2, \dots, p_k$ の順番によらないことが証明できます。

制約

  • $N$ は整数
  • $1 \leq N \leq 10$

入力

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

$N$

出力

問題文の条件を満たすマス目への書き込み方が存在しないなら、$-1$ と出力せよ。存在するなら、そのうちひとつを出力せよ。マス目の $i$ 行 $j$ 列目のマスに書き込む整数を $a_{i,j}$ とすると、以下の形式で出力せよ。

$a_{1,1}$ $a_{2,2}$ $\dots$ $a_{1,2^N}$
$a_{2,1}$ $a_{2,2}$ $\dots$ $a_{2,2^N}$
$\vdots$
$a_{2^N,1}$ $a_{2^N,2}$ $\dots$ $a_{2^N,2^N}$

サンプル

サンプル1
入力
2
出力
7 14 0 8
4 12 2 11
15 9 6 1
13 10 5 3

この書き込み方では $0$ 以上 $2^{4} = 16$ 未満の整数が全てちょうど $1$ 回ずつ書き込まれています。

どの列も列に含まれる要素の XOR が $1$ です。また、どの行も行に含まれる要素の XOR が $1$ です。よって、この書き込み方は正解のひとつです。

サンプル2
入力
1
出力
-1

条件を満たす書き込み方は存在しません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。