XOR on Grid Path
题意
有一个 \(n \times n\) 的整数矩阵，第 \(i\) 行 \(j\) 列的数字为 \(a_{i,j}\)。
你站在 \((1,1)\)，每次你可以从 \((x,y)\) 走到 \((x,y+1)\) 或 \((x+1, y)\)，你要走到 \((n,n)\)，求有多少条路径使得路径上的每个数异或和为 \(0\)。
数据范围
- \(2 \leqslant n \leqslant 20\)
- \(0 \leqslant a_{i, j} \leqslant 2^{30}(1 \leqslant i, j \leqslant n)\)
思路
折半搜索。
折半搜索，顾名思义就是把一条搜索路径分成两条，每条路径先各自考虑，最后将两条路径合起来考虑。
但折半搜索不一定是折半，在某些特定情况下分界点可以不同。
这个题不是特殊题，分界点就在正中间。
不难发现，走 \(n - 1\) 步可以走到的点 \((x,y)\) 要满足 \(x + y = n + 1\)，首先枚举分界点。
折半搜索，两边分别记录一下各自会出现哪些异或和(假设用 \(v\) 数组和 \(g\) 数组存储)，统计满足如下要求的整数对数即可：
- \(i \leqslant |v|, j \leqslant |g|\)。
- \(v_i = g_j\)。
经过计算，我们发现要开 long long 存储。
复杂度
- 时间：\(O(n \times 2^n + n^ 2)\)。
- 空间：\(O(2 ^ n + n ^ 2)\)。
Code
点击查看代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int n, a[30][30];
vector<int> v, g;
ll ans;
void dfs (int x, int y, int z) { // 前半条路径
if (x == 0 || y == 0) {
return ;
}
z ^= a[x][y];
if (x + y == 2) {
v.push_back(z);
return ;
}
dfs(x - 1, y, z), dfs(x, y - 1, z);
}
void dfs2 (int x, int y, int z) { // 后半条路径
if (x > n || y > n) {
return ;
}
z ^= a[x][y];
if (x + y == 2 * n) {
g.push_back(z);
return ;
}
dfs2(x + 1, y, z), dfs2(x, y + 1, z);
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
vector<int> ().swap(v);
vector<int> ().swap(g);// 清空
dfs(i, n + 1 - i, 0);
dfs2(i, n + 1 - i, a[i][n + 1 - i]); // 当前这个点会被算两次，怎么能行，先处理一下
sort(v.begin(), v.end()), sort(g.begin(), g.end());
for (int j : v) {
int l = lower_bound(g.begin(), g.end(), j) - g.begin(), r = upper_bound(g.begin(), g.end(), j) - g.begin(); // 二分求满足要求的整数对数
ans += r - l;
}
}
cout << ans;
return 0;
}