No.2212 One XOR Matrix
タグ : / 解いたユーザー数 82
作問者 :
Shirotsume
/ テスター :
👑 
AngrySadEight
ygussany
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。