No.2663 Zero-Sum Submatrices
Problem Statement
You are given positive integers $n, m$. Construct a $2 ^ n \times 2 ^ m$ matrix $A=(a_{i,j})_{1\leq i\leq 2^n,1\leq j\leq 2^m}$ satisfying all of the following conditions.
- Each integer at least $0$ and less than $2 ^ {n + m}$ appears in $A$ exactly $1$ time.
- For all integers $i,j,k,l$ such that $1\leq i\lt j \leq 2 ^ n, 1\leq k\lt l \leq 2 ^ m$, it holds that $a _ {i, k} \oplus a _ {i, l} \oplus a _ {j, k}\oplus a _ {j, l} = 0$. Here, $x\oplus y$ denotes the bitwise XOR of $x$ and $y$.
If no such $A$ exists, report that fact.
Input
The input is given from standard input in the following format.
$n\ m$
- All inputs are integers
- $1\leq n$
- $1\leq m$
- $n + m \leq 12$
Output
If an $A$ satisfying the conditions exists, on line $i\ (1\leq i\leq 2 ^ n)$ print $a _ {i, 1}, a _ {i, 2}, \ldots, a _ {i, 2 ^ m}$ in this order, separated by spaces. Print a newline after the last line as well. If there are multiple $A$ satisfying the conditions, you may print any of them.
If no $A$ satisfying the conditions exists, print -1 on line $1$, followed by a newline.
Sample
Sample 1
Input
1 2
Output
2 6 1 5 0 4 3 7
Regarding condition $1$, every integer at least $0$ and less than $2 ^ {1 + 2} = 8$ indeed appears $1$ time each.
Condition $2$ also indeed holds, as follows.
- [When $(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$
- [When $(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$
- [When $(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$
- [When $(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$
- [When $(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$
- [When $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。
cureskol