#atk3ax. Xor-Paths

时间限制：3 s       空间限制：250 MiB       标签： 搜索 双向搜索 暴力 位运算 CodeForces 

算法难度等级：5       思维难度等级：5       实现难度等级：5

题目大意

给定一个 $n\times m$ 的地图 $a_{i,\ j}$。

一条从左上角到右下角的路径，满足每次都只能向右或向下走，计算路径中经过的格子的 $a$ 值的异或和。求这个和等于 $k$ 的路径条数。

$1\leq n,\ m\leq 20$，$0\leq k\leq 10^{18}$

题目描述

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 \leq n,\ m\leq 20$, $0\leq k\leq 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 \leq a_{i, j} \leq 10^{18}$).

输出格式

Print one integer — the number of paths from $(1,\ 1)$ to $(n,\ m)$ with xor sum equal to $k$.

样例输入输出

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

3

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

5

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

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