AT_abc271_f [ABC271F] XOR on Grid Path

题目描述

有一个 $N$ 行 $N$ 列的方格，从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作 $(i, j)$。
每个格子 $(i, j)$ 上写有一个非负整数 $a_{i, j}$。

你可以从格子 $(i, j)$ 移动到 $(i+1, j)$ 或 $(i, j+1)$，但不能移出方格范围。

请计算，从 $(1, 1)$ 出发，通过若干次移动到达 $(N, N)$ 的所有路径中，经过的所有格子（包括 $(1, 1)$ 和 $(N, N)$）上所写的整数的异或和为 $0$ 的路径总数。

异或的定义如下：对于整数 $a, b$，它们的异或 $a \oplus b$ 定义为：将 $a, b$ 用二进制表示后，每一位上如果只有一方为 $1$，则该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（因为 $011 \oplus 101 = 110$）。
一般地，$k$ 个整数 $p_1, \dots, p_k$ 的异或为 $(\cdots((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$，并且可以证明其结果与顺序无关。

输入格式

输入通过标准输入给出，格式如下：

$N$
$a_{1, 1}\ a_{1, 2}\ \ldots\ a_{1, N}$
$\vdots$
$a_{N, 1}\ a_{N, 2}\ \ldots\ a_{N, N}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 5 2
7 0 5
4 2 3

输出 #1

2

输入输出样例 #2

输入 #2

2
1 2
2 1

输出 #2

0

输入输出样例 #3

输入 #3

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

输出 #3

24307

说明/提示

数据范围

• $2 \leq N \leq 20$
• $0 \leq a_{i, j} < 2^{30}\ (1 \leq i, j \leq N)$
• 输入均为整数

样例解释 1

有以下两条路径满足条件：

• $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)$
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$

由 ChatGPT 4.1 翻译