Official Analysis (C++)

Alternative Explanation

This problem is actually pretty similar to the focus problem in the meet-in-the-middle module. As the official editorial states, we can maneuver the grid in exactly $n + m - 2$ moves. Thus, we can split the moves up into two. If we have $x$ as the XOR sum from one side, then we are adding how many instances of $k ⊕x$ there are on the other side. One side is starting from $(1, 1)$ and making our way down, and the other side is from $(n, m)$ and making our way up. Each side will have half the moves.

Implementation

The official solution uses DFS, but that isn't needed. We can simply loop over subsets. Note that at the end where we are counting the total number of ways, we have $1$ less than the total number of moves. This is because it takes one extra move to make the two sides meet.

Time Complexity: $O(2^{\frac{n + m - 2}{2}} \cdot \frac{n + m - 2}{2})$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int n, m;
	ll k;
	cin >> n >> m >> k;
	vector<vector<ll>> grid(n, vector<ll>(m));
	for (int i = 0; i < n; i++) {