Xor-Paths

题意翻译

给出一个 n × m 的网格，每个格子上有权值 a[i][j]，现在zhqwq要从 (1,1) 走到 (n,m)去抱走wyz，每次只能向右或向下走， 沿路计算异或和，求异或和等于 k 的路径数。 ## Input 第一行包含三个整数 n,m,k(1 ≤ n,m ≤ 20; $0 \le k \le 10^{18}$)。 接下来 n 行，每行包含 m 个整数，表示格上的权值。 ## Output 1个整数，表示路径数。

题目描述

There is a rectangular grid of size $ n \times m $ . Each cell has a number written on it; the number on the cell ( $ i, j $ ) is $ a_{i, j} $ . Your task is to calculate the number of paths from the upper-left cell ( $ 1, 1 $ ) to the bottom-right cell ( $ n, m $ ) meeting the following constraints: - You can move to the right or to the bottom only. Formally, from the cell ( $ i, j $ ) you may move to the cell ( $ i, j + 1 $ ) or to the cell ( $ i + 1, j $ ). The target cell can't be outside of the grid. - The xor of all the numbers on the path from the cell ( $ 1, 1 $ ) to the cell ( $ n, m $ ) must be equal to $ k $ (xor operation is the bitwise exclusive OR, it is represented as '^' in Java or C++ and "xor" in Pascal). Find the number of such paths in the given grid.

输入输出格式

输入格式

The first line of the input contains three integers $ n $ , $ m $ and $ k $ ( $ 1 \le n, m \le 20 $ , $ 0 \le k \le 10^{18} $ ) — the height and the width of the grid, and the number $ k $ . The next $ n $ lines contain $ m $ integers each, the $ j $ -th element in the $ i $ -th line is $ a_{i, j} $ ( $ 0 \le a_{i, j} \le 10^{18} $ ).

输出格式

Print one integer — the number of paths from ( $ 1, 1 $ ) to ( $ n, m $ ) with xor sum equal to $ 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

说明

All the paths from the first example: - $ (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) $ . All the paths from the second example: - $ (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) $ .