分数: 500 点
问题陈述
有一个网格 N 行和 N 列。 我们表示为 (i, j) 广场 i-th (1 \leq i \leq N) 从顶部开始行, j-th (1 \leq j \leq N) 列从左起。
广场 (i, j) 有一个非负整数
上面写着 a_{i, j} 。
当你在广场时 (i, j),您可以移动到任一方格 (i+1, j) or (i, j+1)。 在这里,你不可以走出网格。
求从广场出发的出行方式数 (1, 1) 到正方形 (N, N) 使得写在所访问的方格上的整数的异逻辑和(包括 (1, 1) 和 (N, N))是 0.
什么是异逻辑和?
异或逻辑和 a \oplus b 两个整数 a 和 b 定义如下。- 的 2^k的地点 (k \geq 0) 的二进制表示法 a \oplus b is 1 如果恰好是其中之一 2^k在二进制表示法中的位置 a 和 b is 1;否则,就是 0.
一般来说,异逻辑和 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.
约束
- 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}
输出
打印答案。
示例输入 1
3 1 5 2 7 0 5 4 2 3
示例输出 1
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
2 1 2 2 1
示例输出 2
0
示例输入 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