Xor-Paths
Contest: Codeforces Round 498 (Div. 3)
Difficulty rating: 2100
Tags: bitmasks, brute force, dp, meet-in-the-middle

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.

Input format:
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}$$$).

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
3 3 11
2 1 5
7 10 0
12 6 4

Example output:
3

Example input:
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1

Example output:
5

Editorial:
This is a typical problem on the meet-in-the-middle technique.
The number of moves we will made equals $$$n + m - 2$$$. So if $$$n + m$$$ would be small enough (25 is the upper bound, I think), then we can just run recursive backtracking in $$$O(2^{n + m - 2})$$$ or in $$$O($$$$$${n + m - 2}\choose{m - 1}$$$$$$ \cdot (n + m - 2))$$$ to iterate over all binary masks of lengths $$$n + m - 2$$$ containing exactly $$$m - 1$$$ ones and check each path described by such mask ($$$0$$$ in this mask is the move to the bottom and $$$1$$$ is the move to the right) if its xor is $$$k$$$.
But it is too slow. So let's split this mask of $$$n + m - 2$$$ bits into two parts — the left part will consist of $$$mid = \lfloor\frac{n + m - 2}{2}\rfloor$$$ bits and the right part will consist of $$$n + m - 2 - mid$$$ bits. Note that each left mask (and each right mask too) uniquely describes the endpoint of the path and the path itself.
Let's carry $$$n \times m$$$ associative arrays $$$cnt$$$ where $$$cnt_{x, y, c}$$$ for the endpoint $$$(x, y)$$$ and xor $$$c$$$ will denote the number of paths which end in the cell $$$(x, y)$$$ having xor $$$c$$$.
Let's run recursive backtracking which will iterate over paths starting from the cell $$$(1, 1)$$$ and move to the right or to the bottom and maintain xor of the path. If we made $$$mid$$$ moves and we are currently in the cell $$$(x, y)$$$ with xor $$$c$$$ right now, set $$$cnt_{x, y, c} := cnt_{x, y, c} + 1$$$ and return from the function. Otherwise try to move to the bottom or to the right changing xor as needed.
Let's run another recursive backtracking which will iterate over paths starting from the cell $$$(n, m)$$$ and move to the left or to the top and maintain xor of the path except the last cell. The same, if we made $$$n + m - 2 - mid$$$ moves and we are currently in the cell $$$(x, y)$$$ with xor $$$c$$$ right now, let's add $$$cnt_{x, y, k ^ c}$$$ to the answer (obvious, that way we "complement" our xor from the right part of the path with the suitable xor from the left part of the path). Otherwise try to move to the left or to the top changing xor as needed.
So, this is the meet-in-the-middle technique (at least the way I code it).
Overall complexity is $$$O(2^{\frac{n + m - 2}{2}} \cdot \frac{n + m - 2}{2})$$$.