很明明白白的一道搜索题

60分做法

首先我们最容易想到的做法是什么？ 小学二年级教过，从起点出发，然后DFS/BFS一下到$(n,m)$的所有路径的异或和，然后判断是否等于$k$，然后$ans$++即可。

（注意：十年OI一场空，不开__见祖宗）

但是这样做只能得60分，为什么？时间超限了！

分析时间复杂度

我们由于只能往下或者往右运动，所以说总步数是固定的，令总步数为$S$，那么$S=n+m-2$。而选$n-1$步往下面走，直接列出时间复杂度，然后还有异或求和操作，时间复杂度为：$O(C_{n+m-2}^{n-1})$ （也可以理解为$O(2^{n+m})$）

那么，在极限情况下当$n=25,m=25$时，显然超过了题目要求.

60分做法：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 25;
unsigned long long n, m, k; int ans = 0;
unsigned long long a[maxn][maxn];
void dfs(unsigned int x, unsigned int y, unsigned long long xorans);
int main(void) {
	freopen("xorpath.in", "r", stdin);
	freopen("xorpath.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m >> k;
	for (unsigned int i = 1;i <= n;i++) {
		for (unsigned int j = 1;j <= m;j++) {
			cin >> a[i][j];
		}
	}
	dfs(1, 1, a[1][1]);
	cout << ans << '\n';
	return 0;
}
void dfs(unsigned int x, unsigned int y, unsigned long long xorans) {
	if (xorans == k && x == n && y == m) {
		ans++; return;
	}
	if (x > n || y > m) return;
	if (x < 1 || y < 1) return;
	dfs(x + 1, y, xorans ^ a[x + 1][y]);
	dfs(x, y + 1, xorans ^ a[x][y + 1]); 
}

AC满分做法(标程还是太权威了)

这里先简单介绍一下双向搜索吧。或者不想看的直接点这里。 折半搜索，又叫“二分搜索”，顾名思义，就是用两个搜索函数，一个从起点出发到中间，然后另一个函数从终点出发，其中相遇的点来进行统计。

我们可以用一个unorderd_map来统计每一个到这个点的异或值路径的条数，比如$[5][5][3]=2$代表着$(5,5)$这个点异或值为$3$的点有2条。然后在第二个DFS函数中来进行还原，但是有一个需要注意的点是，中间的点会被异或两次，如果没有进行判断的话，会直接导致答案数变成$0$，所以我们要进行特判还原，把两个$M$对于答案的影响抵消掉。

同时注意不要越界，进行判断。

在基础上，直接砍掉了指数上的时间复杂度，时间复杂度是$O(2^{\frac{(n+m)}{2}})$，换算下来直接少了上亿倍。

100分做法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
typedef unsigned long long ULL;
int n, m; 
ULL k, a[maxn][maxn], ans;
unordered_map<ULL, int> res[maxn][maxn];
int total_step, half_step;
void dfs1(int x, int y, ULL now, int step);
void dfs2(int x, int y, ULL now, int step);
int main(void) {
    freopen("xorpath.in", "r", stdin);
    freopen("xorpath.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m >> k;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			cin >> a[i][j];
		}
	}
	total_step = n + m - 2, half_step = total_step / 2;
	dfs1(1, 1, a[1][1], 0);
	dfs2(n, m, a[n][m], 0);
	cout << ans;
	return 0;
}
void dfs1(int x, int y, ULL now, int step) {
	if (step == half_step) {
		res[x][y][now]++;
		return;
	}
	if (x + 1 <= n) dfs1(x + 1, y, now ^ a[x + 1][y], step + 1);
	if (y + 1 <= m) dfs1(x, y + 1, now ^ a[x][y + 1], step + 1);
}
void dfs2(int x, int y, ULL now, int step) {
	if (step == total_step - half_step) {
		ans += res[x][y][k ^ now ^ a[x][y]]; // X ^ Y = Z
		return;
	}
	if (x - 1 >= 1) dfs2(x - 1, y, now ^ a[x - 1][y], step + 1);
	if (y - 1 >= 1) dfs2(x, y - 1, now ^ a[x][y - 1], step + 1);
}

最后附AC记录。