ABC 271 F – XOR on Grid Path题意：
给出20 * 20的地图，每个点上都有一个点权，保证为正整数。请问从(1, 1)走到(n, n)且路径上所有点权异或和为0的路径有多少条。
思路：
本题利用了meet in the mid的思想。因为是(1, 1)到(n, n)，所以一定会在某个中间的地方相遇。
走到某点(x, y)会有很多种路径，以及很多个不同的异或和值。因为从(1, 1)走到(n, n)一共是2 * n步。
我们预处理从(1, 1)只向右下走，走到(x, y)，且步数为n的时候停止，并将异或和加入\(mp[x][y][val] ++\)。
然后再从(n, n)只向左上走，走到(x, y)的时候，如果此时的异或和有这样的值存在\(mp[x][y]\)，就把方案数加上。
这样做的时间复杂度是2 * C(20, 10)，还有一个map的log复杂度。（用umap可能被卡到O(n)，在CF慎用）。
实现：
\(map [x][y]\)为走到(x, y)的时候，他的不同的值和其方案数。
int n;int c[22][22];map mp[22][22];int res = 0;void dfs1(int x, int y, int step, int sum){ if (step == n) { mp[x][y][sum ^ c[x][y]]++; //最后一步 return; } if (x + 1 <= n) dfs1(x + 1, y, step + 1, sum ^ c[x][y]); if (y + 1 = 1) dfs2(x - 1, y, step + 1, sum ^ c[x][y]); if (y - 1 >= 1) dfs2(x, y - 1, step + 1, sum ^ c[x][y]);}signed main(){ ios::sync_with_stdio(false);cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j > c[i][j]; dfs1(1, 1, 1, 0); dfs2(n, n, 1, 0); cout << res << '\n';}