CF1006F Xor-Paths

有一个大小为 $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, 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)$。 由 ChatGPT 4.1 翻译