当前没有测试数据。

F - XOR on Grid Path

得分: $500$ 分

问题描述

有一个 $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 和 b 的二进制表示中，若对应位上，a 和 b 一个为 1 而另一个为 0，则异或和的该位为 1，否则为 0。

例如，$3 \oplus 5 = 6$ （二进制表示：$011 \oplus 101 = 110$）。

限制

• $2 \leq N \leq 20$
• $0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)$
• 输入中的所有数都是整数。

---

输入

从标准输入读入数据的格式如下:

$N$

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

$\vdots$

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

输出

输出结果。

---

3
1 5 2
7 0 5
4 2 3

2

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

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

---

2
1 2
2 1

0

---

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

24307