[Codeforces 1006.F] Xor-Paths（meet in the middle）

Posted on | In ,
Codeforces 1006F

题目

链接

解题思路

最暴力的搜索很容易实现，但是从 $(1,1)$ 到 $(n,m)$ 有 $C_{n+m-2}^{n-1}$ 种走法，大概是 $10^{11}$ 左右的复杂度，显然会 TLE。
我们可以用 meet in the middle 来优化搜索。具体的，从 $(1,1)$ 搜索到一个折半点就停止搜索，再从 $(n.n)$ 搜索到折半点，然后用折半点的信息统计答案。折半点可以选择 $x+y=(n+m)/2$ 的点以保证搜索深度。
对于这道题，在每一个折半点处开一个map，统计第一次搜索后得到的异或值及其出现次数；第二次搜索到同一个折半点时，统计符合答案的异或值的次数即可。
运用 meet in the middle，把这道题的时间复杂度降到了 $10^5$ 数量级。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>

using namespace std;

//此处省略 define 的一些东西和读入输出优化

const int N = 25;
int n, m;
LL k, a[N][N], ans;
map<LL, LL> v[N][N];

void dfs1(int x, int y, LL val){
	if(x + y == (n + m) / 2 + 1){
		v[x][y][val]++;
		return;
	}
	if(x + 1 <= n)
		dfs1(x + 1, y, val ^ a[x + 1][y]);
	if(y + 1 <= m)
		dfs1(x, y + 1, val ^ a[x][y + 1]);
}

void dfs2(int x, int y, LL val){
	if(x + y == (n + m) / 2 + 1){
		ans += v[x][y][val ^ a[x][y] ^ k];
		return;
	}
	if(x - 1 >= 1)
		dfs2(x - 1, y, val ^ a[x - 1][y]);
	if(y - 1 >= 1)
		dfs2(x, y - 1, val ^ a[x][y - 1]);
}

int main(){
	in(n); in(m); in(k);
	fo1(i, 1, n)
		fo1(j, 1, m)
			in(a[i][j]);
	dfs1(1, 1, a[1][1]);
	dfs2(n, m, a[n][m]);
	out(ans);
	return 0;
}