No.2663 Zero-Sum Submatrices
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 131
作問者 :
suisen
/ テスター :
👑 
p-adic
cureskol
👑 
ygussany
タグ : / 解いたユーザー数 131
作問者 :
suisen
/ テスター :
👑 p-adic
cureskol
👑 ygussany
問題文最終更新日: 2024-02-29 21:39:14
問題文
正整数 $n, m$ が与えられます。以下の条件を全て満たす $2 ^ n \times 2 ^ m$ 行列 $A=(a_{i,j})_{1\leq i\leq 2^n,1\leq j\leq 2^m}$ を構築してください。
- $0$ 以上 $2 ^ {n + m}$ 未満の整数がちょうど $1$ つずつ $A$ に含まれる。
- 全ての $1\leq i\lt j \leq 2 ^ n, 1\leq k\lt l \leq 2 ^ m$ なる整数 $i,j,k,l$ に対して、$a _ {i, k} \oplus a _ {i, l} \oplus a _ {j, k}\oplus a _ {j, l} = 0$ が成り立つ。ここで、$x\oplus y$ は $x$ と $y$ のビット毎の排他的論理和です。
そのような $A$ が存在しない場合は、その旨を報告してください。
入力
入力は以下の形式で標準入力から与えられる。
$n\ m$
- 入力は全て整数で与えられる
- $1\leq n$
- $1\leq m$
- $n + m \leq 12$
出力
条件を満たす $A$ が存在する場合は、$i\ (1\leq i\leq 2 ^ n)$ 行目には $a _ {i, 1}, a _ {i, 2}, \ldots, a _ {i, 2 ^ m}$ をこの順番で空白区切りで出力してください。最終行のあとも改行してください。条件を満たす $A$ が複数存在する場合はどれを出力しても構いません。
条件を満たす $A$ が存在しない場合は、$1$ 行目に -1 を出力して改行してください。
サンプル
サンプル1
入力
1 2
出力
2 6 1 5 0 4 3 7
$1$ つめの条件に関して、確かに $0$ 以上 $2 ^ {1 + 2} = 8$ 未満の整数が全て $1$ 回ずつ現れています。
$2$ つめの条件についても次のように確かに成り立っています。
- 【$(i,j,k,l)=(1,2,1,2)$ のとき】$a _ {1, 1} \oplus a _ {1, 2} \oplus a _ {2, 1}\oplus a _ {2, 2} = 2 \oplus 6 \oplus 0\oplus 4 = 0$
- 【$(i,j,k,l)=(1,2,1,3)$ のとき】$a _ {1, 1} \oplus a _ {1, 3} \oplus a _ {2, 1}\oplus a _ {2, 3} = 2 \oplus 1 \oplus 0\oplus 3 = 0$
- 【$(i,j,k,l)=(1,2,1,4)$ のとき】$a _ {1, 1} \oplus a _ {1, 4} \oplus a _ {2, 1}\oplus a _ {2, 4} = 2 \oplus 5 \oplus 0\oplus 7 = 0$
- 【$(i,j,k,l)=(1,2,2,3)$ のとき】$a _ {1, 2} \oplus a _ {1, 3} \oplus a _ {2, 2}\oplus a _ {2, 3} = 6 \oplus 1 \oplus 4\oplus 3 = 0$
- 【$(i,j,k,l)=(1,2,2,4)$ のとき】$a _ {1, 2} \oplus a _ {1, 4} \oplus a _ {2, 2}\oplus a _ {2, 4} = 6 \oplus 5 \oplus 4\oplus 7 = 0$
- 【$(i,j,k,l)=(1,2,3,4)$ のとき】$a _ {1, 3} \oplus a _ {1, 4} \oplus a _ {2, 3}\oplus a _ {2, 4} = 1 \oplus 5 \oplus 3\oplus 7 = 0$
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。