← 返回题目列表

Codeforces · 1006/F

F. 异或路径

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

有一个大小为 $$$n \times m$$$ 的矩形网格。每个单元格上都写有一个数字;单元格 ($$$i, j$$$) 上的数字是 $$$a_{i, j}$$$。您的任务是计算从左上角单元格 ($$$1, 1$$$) 到右下角单元格 ($$$n, m$$$) 的路径数,且满足以下约束:

- 您只能移动到右侧或底部。形式上,从单元格 ($$$i, j$$$) 可以移动到单元格 ($$$i, j + 1$$$) 或单元格 ($$$i + 1, j$$$)。目标单元格不能位于网格之外。
- 从单元格 ($$$1, 1$$$) 到单元格 ($$$n, m$$$) 的路径上的所有数字的异或必须等于 $$$k$$$(异或运算是按位异或,在 Java 或 C++ 中表示为 '^',在 Pascal 中表示为“xor”)。

找出给定网格中此类路径的数量。

输入

输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m \le 20$$$, $$$0 \le k \le 10^{18}$$$) — 网格的高度和宽度,以及数字 $$$k$$$。

接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个整数,第 $$$i$$$ 行中的第 $$$j$$$ 元素是 $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 10^{18}$$$)。

输出

打印一个整数 — 从 ($$$1, 1$$$) 到 ($$$n, m$$$) 的路径数,异或和等于 $$$k$$$。

示例

输入 #1

3 3 11
2 1 5
7 10 0
12 6 4

输出 #1

3

输入 #2

3 4 2
1 3 3 3
0 3 3 2
3 0 1 1

输出 #2

5

输入 #3

3 4 1000000000000000000
1 3 3 3
0 3 3 2
3 0 1 1

输出 #3

0

注意

第一个示例中的所有路径:

- $$$(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$$$;
- $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$$$;
- $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$$$。

第二个示例中的所有路径:

- $$$(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$$$;
- $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$$$;
- $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$$$;
- $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$$$;
- $$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$$$。