No.2212 One XOR Matrix
タグ : / 解いたユーザー数 81
作問者 :
Shirotsume
/ テスター :
👑 
ygussany
Problem Statement
There is a $2^N \times 2^N$ grid. In each cell of this grid, you write $1$ integer that is at least $0$ and less than $2^{2N}$. Here, for every integer at least $0$ and less than $2^{2N}$, there must be exactly $1$ cell in which that integer is written.
Determine whether there exists a way of writing such that, for every column, the bitwise XOR of the elements in the column is $1$, and, for every row, the bitwise XOR of the elements in the row is $1$. If one exists, construct $1$ such way.
What is bitwise XOR? (click to expand)
For $2$ non-negative integers $X, Y$, the bitwise XOR of $X$ and $Y$, $X \oplus Y$, is defined as follows.
- When $X \oplus Y$ is written in base $2$, the digit in the $2^k$ $(k \geq 0)$ place is $1$ if exactly one of the digit in the $2^k$ place of $X$ in base $2$ and the digit in the $2^k$ place of $Y$ in base $2$ is $1$, and $0$ otherwise.
For example, $3 \oplus 5 = 6, 1 \oplus 1 = 0$.
In general, the bitwise XOR of $k$ non-negative integers $p_1, p_2, \dots, p_k$ is defined as $( \dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots) \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, \dots, p_k$.
Constraints
- $N$ is an integer
- $1 \leq N \leq 10$
Input
The input is given from standard input in the following format.
$N$
Output
If there is no way of writing integers in the grid that satisfies the conditions in the problem statement, print $-1$. If one exists, print any one of them. Letting $a_{i,j}$ be the integer written in the cell at row $i$, column $j$ of the grid, print in the following format.
$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}$
Sample
Sample 1
Input
2
Output
7 14 0 8 4 12 2 11 15 9 6 1 13 10 5 3
In this way of writing, every integer at least $0$ and less than $2^{4} = 16$ is written exactly $1$ time.
In every column, the XOR of the elements in the column is $1$. Also, in every row, the XOR of the elements in the row is $1$. Therefore, this way of writing is one of the correct answers.
Sample 2
Input
1
Output
-1
No way of writing satisfies the conditions.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。