Score : $500$ points

问题描述

存在一个 $N$ 行和 $N$ 列的网格。我们用 $(i, j)$ 表示从上到下的第 $i$ 行（$1 \leq i \leq N$）以及从左到右的第 $j$ 列（$1 \leq j \leq N$）的方格。

在方格 $(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$ 在二进制表示中 $2^k$ 位（$k \geq 0$）恰有一个为 $1$，则 $a \oplus b$ 的二进制表示中 $2^k$ 位为 $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)$。我们可以证明这个结果与 $p_1, \dots, p_k$ 的顺序无关。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a grid with $N$ rows and $N$ columns. We denote by $(i, j)$ the square at the $i$-th $(1 \leq i \leq N)$ row from the top and $j$-th $(1 \leq j \leq N)$ column from the left.
Square $(i, j)$ has a non-negative integer $a_{i, j}$ written on it.

When you are at square $(i, j)$, you can move to either square $(i+1, j)$ or $(i, j+1)$. Here, you are not allowed to go outside the grid.

Find the number of ways to travel from square $(1, 1)$ to square $(N, N)$ such that the exclusive logical sum of the integers written on the squares visited (including $(1, 1)$ and $(N, N)$) is $0$.

What is the exclusive logical sum? The exclusive logical sum $a \oplus b$ of two integers $a$ and $b$ is defined as follows.

• The $2^k$'s place ($k \geq 0$) in the binary notation of $a \oplus b$ is $1$ if exactly one of the $2^k$'s places in the binary notation of $a$ and $b$ is $1$; otherwise, it is $0$.

For example, $3 \oplus 5 = 6$ (In binary notation: $011 \oplus 101 = 110$).
In general, the exclusive logical sum of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$. We can prove that it is independent of the order of $p_1, \dots, p_k$.

Constraints

• $2 \leq N \leq 20$
• $0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$

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

$\vdots$

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

Output

Print the answer.

Sample Input 1

3
1 5 2
7 0 5
4 2 3

Sample Output 1

2

The following two ways satisfy the condition:

• $(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)$.

Sample Input 2

2
1 2
2 1

Sample Output 2

0

Sample Input 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

Sample Output 3

24307

update @ 2024/3/10 11:26:37