← 返回题目列表

AtCoder · abc271_f

I. 网格路径上的异或

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

分数: 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.
例如, 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.

约束

  • 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