CF1006F.Xor-Paths

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

说明/提示

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)$ .

首页