← 返回题目列表

Codeforces · 1628/C

C. 网格异或

中文机器翻译题面 查看原题

注意:集合 $$$\{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 - k|,则 $$$i$$$ 行和 $$$j$$$ 列中的单元格是 $$$k$$$ 行和 $$$l$$$ 列中的单元格的邻居= 1$$$ 且 $$$j = l$$$,或者如果 $$$i = k$$$ 且 $$$|j - l| = 1$$$。

为了恢复他的网格,维克多向你寻求帮助。你能用维克多记得的信息来找到整个网格的异或和吗?

可以证明答案是唯一的。

输入

输入的第一行包含一个整数 $$$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$$$。

黑客格式

要破解解决方案,请使用以下格式:

第一行应包含一个整数 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$$$。

输出

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

示例

输入 #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

注意

对于第一个测试用例,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$$$