A14805. Grid Xor
编程题
普及/提高-
知识点
题目描述
Note: The XOR-sum of set $\{s_1,s_2,\ldots,s_m\}$ is defined as $s_1 \oplus s_2 \oplus \ldots \oplus s_m$ , where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
After almost winning IOI, Victor bought himself an $n\times n$ grid containing integers in each cell. $n$ is an even integer. The integer in the cell in the $i$ -th row and $j$ -th column is $a_{i,j}$ .
Sadly, Mihai stole the grid from Victor and told him he would return it with only one condition: Victor has to tell Mihai the XOR-sum of all the integers in the whole grid.
Victor doesn't remember all the elements of the grid, but he remembers some information about it: For each cell, Victor remembers the XOR-sum of all its neighboring cells.
Two cells are considered neighbors if they share an edge — in other words, for some integers $1 \le i, j, k, l \le n$ , the cell in the $i$ -th row and $j$ -th column is a neighbor of the cell in the $k$ -th row and $l$ -th column if $|i - k| = 1$ and $j = l$ , or if $i = k$ and $|j - l| = 1$ .
To get his grid back, Victor is asking you for your help. Can you use the information Victor remembers to find the XOR-sum of the whole grid?
It can be proven that the answer is unique.
After almost winning IOI, Victor bought himself an $n\times n$ grid containing integers in each cell. $n$ is an even integer. The integer in the cell in the $i$ -th row and $j$ -th column is $a_{i,j}$ .
Sadly, Mihai stole the grid from Victor and told him he would return it with only one condition: Victor has to tell Mihai the XOR-sum of all the integers in the whole grid.
Victor doesn't remember all the elements of the grid, but he remembers some information about it: For each cell, Victor remembers the XOR-sum of all its neighboring cells.
Two cells are considered neighbors if they share an edge — in other words, for some integers $1 \le i, j, k, l \le n$ , the cell in the $i$ -th row and $j$ -th column is a neighbor of the cell in the $k$ -th row and $l$ -th column if $|i - k| = 1$ and $j = l$ , or if $i = k$ and $|j - l| = 1$ .
To get his grid back, Victor is asking you for your help. Can you use the information Victor remembers to find the XOR-sum of the whole grid?
It can be proven that the answer is unique.
输入格式
The first line of the input contains a single integer $t$ ( $1 \le t \le 100$ ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single even integer $n$ ( $2 \leq n \leq 1000$ ) — the size of the grid.
Then follows $n$ lines, each containing $n$ integers. The $j$ -th integer in the $i$ -th of these lines represents the XOR-sum of the integers in all the neighbors of the cell in the $i$ -th row and $j$ -th column.
It is guaranteed that the sum of $n$ over all test cases doesn't exceed $1000$ and in the original grid $0 \leq a_{i, j} \leq 2^{30} - 1$ .
Hack Format
To hack a solution, use the following format:
The first line should contain a single integer t ( $1 \le t \le 100$ ) — the number of test cases.
The first line of each test case should contain a single even integer $n$ ( $2 \leq n \leq 1000$ ) — the size of the grid.
Then $n$ lines should follow, each containing $n$ integers. The $j$ -th integer in the $i$ -th of these lines is $a_{i,j}$ in Victor's original grid. The values in the grid should be integers in the range $[0, 2^{30}-1]$
The sum of $n$ over all test cases must not exceed $1000$ .
The first line of each test case contains a single even integer $n$ ( $2 \leq n \leq 1000$ ) — the size of the grid.
Then follows $n$ lines, each containing $n$ integers. The $j$ -th integer in the $i$ -th of these lines represents the XOR-sum of the integers in all the neighbors of the cell in the $i$ -th row and $j$ -th column.
It is guaranteed that the sum of $n$ over all test cases doesn't exceed $1000$ and in the original grid $0 \leq a_{i, j} \leq 2^{30} - 1$ .
Hack Format
To hack a solution, use the following format:
The first line should contain a single integer t ( $1 \le t \le 100$ ) — the number of test cases.
The first line of each test case should contain a single even integer $n$ ( $2 \leq n \leq 1000$ ) — the size of the grid.
Then $n$ lines should follow, each containing $n$ integers. The $j$ -th integer in the $i$ -th of these lines is $a_{i,j}$ in Victor's original grid. The values in the grid should be integers in the range $[0, 2^{30}-1]$
The sum of $n$ over all test cases must not exceed $1000$ .
输出格式
For each test case, output a single integer — the XOR-sum of the whole grid.
输入输出样例
输入 #1
3 2 1 5 5 1 4 1 14 8 9 3 1 5 9 4 13 11 1 1 15 4 11 4 2 4 1 6 3 7 3 10 15 9 4 2 12 7 15 1
输出 #1
4 9 5
说明/提示
For the first test case, one possibility for Victor's original grid is:
$1$ $3$ $2$ $4$ For the second test case, one possibility for Victor's original grid is:
$3$ $8$ $8$ $5$ $9$ $5$ $5$ $1$ $5$ $5$ $9$ $9$ $8$ $4$ $2$ $9$ For the third test case, one possibility for Victor's original grid is:
$4$ $3$ $2$ $1$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $8$ $9$ $9$ $1$
$1$ $3$ $2$ $4$ For the second test case, one possibility for Victor's original grid is:
$3$ $8$ $8$ $5$ $9$ $5$ $5$ $1$ $5$ $5$ $9$ $9$ $8$ $4$ $2$ $9$ For the third test case, one possibility for Victor's original grid is:
$4$ $3$ $2$ $1$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $8$ $9$ $9$ $1$