CF1628C Grid Xor

题目描述

注意：集合 $\{s_1,s_2,\ldots,s_m\}$ 的异或和定义为 $s_1 \oplus s_2 \oplus \ldots \oplus s_m$，其中 $\oplus$ 表示按位异或运算。

在几乎赢得 IOI 之后，Victor 给自己买了一个 $n\times n$ 的网格，每个格子里都有一个整数。$n$ 是一个偶数。第 $i$ 行第 $j$ 列格子中的整数为 $a_{i,j}$。

不幸的是，Mihai 偷走了 Victor 的网格，并告诉他只有在一个条件下才会归还：Victor 必须告诉 Mihai 整个网格所有整数的异或和。

Victor 并不记得网格中的所有元素，但他记得一些信息：对于每个格子，Victor 记得它所有相邻格子的异或和。

如果两个格子有公共边，则认为它们是相邻的——换句话说，对于某些整数 $1 \le i, j, k, l \le n$，第 $i$ 行第 $j$ 列的格子与第 $k$ 行第 $l$ 列的格子相邻，当且仅当 $|i - k| = 1$ 且 $j = l$，或 $i = k$ 且 $|j - l| = 1$。

为了拿回他的网格，Victor 向你寻求帮助。你能否利用 Victor 记得的信息，求出整个网格的异或和？

可以证明答案是唯一的。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 100$）——表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个偶数 $n$（$2 \leq n \leq 1000$）——网格的大小。

接下来有 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个整数表示第 $i$ 行第 $j$ 列格子的所有相邻格子的异或和。

保证所有测试用例中 $n$ 的总和不超过 $1000$，且原始网格中 $0 \leq a_{i, j} \leq 2^{30} - 1$。

Hack 格式

要 hack 一个解，使用如下格式：

第一行应包含一个整数 $t$（$1 \le t \le 100$）——测试用例数量。

每个测试用例的第一行应包含一个偶数 $n$（$2 \leq n \leq 1000$）——网格的大小。

接下来有 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个整数为 Victor 原始网格中的 $a_{i,j}$。网格中的值应为 $[0, 2^{30}-1]$ 范围内的整数。

所有测试用例中 $n$ 的总和不超过 $1000$。

输出格式

对于每个测试用例，输出一个整数——整个网格的异或和。

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

4
9
5

说明/提示

对于第一个测试用例，Victor 原始网格的一种可能情况为：

$1$ $3$ $2$ $4$

对于第二个测试用例，Victor 原始网格的一种可能情况为：

$3$ $8$ $8$ $5$
$9$ $5$ $5$ $1$
$5$ $5$ $9$ $9$
$8$ $4$ $2$ $9$

对于第三个测试用例，Victor 原始网格的一种可能情况为：

$4$ $3$ $2$ $1$
$1$ $2$ $3$ $4$
$5$ $6$ $7$ $8$
$8$ $9$ $9$ $1$

由 ChatGPT 4.1 翻译