XOR on Grid Path（Meet in the Middle）

题意

给定一个\(N \times N\)的方阵，元素为\(a_{ij}\)。

最初位于\((1,1)\)处，每次只能往右或往上走一格。

问走到\((N,N)\)时，途径元素异或和为\(0\)的方案数为多少。

题目链接：https://atcoder.jp/contests/abc271/tasks/abc271_f

数据范围

\(2 \leq N \leq 20\)
\(0 \leq a_{ij} < 2^{30}\)

思路

这道题直接爆搜肯定会TLE，因此需要使用Meet in the Middle技巧。

Meet in the Middle就是从前往后搜一半，从后往前搜一半，然后再将结果进行合并。时间复杂度可以将原来的\(O(2^{2N})\)变为\(O(N2^N)\)

具体来说，从前往后搜\(i+j \leq N+1\)的所有格子，并将异或值以及方案数记录到map中。再从后往前搜\(i+j > N+1\)的所有格子，并将异或值以及方案数记录到另一个map中。

枚举所有\(i+j=N+1\)的格子，统计答案。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 25;

int n;
int a[N][N];
bool st[N][N];
map<int, ll> mp1[N][N], mp2[N][N];

int dx[2] = {0, 1}, dy[2] = {1, 0};

void bfs1()
{
    queue<pii> que;
    que.push({1, 1});
    st[1][1] = true;
    while(que.size()) {
        auto t = que.front();
        int tx = t.first, ty = t.second;
        que.pop();
        for(int i = 0; i < 2; i ++) {
            int x = tx + dx[i], y = ty + dy[i];
            if(x < 1 || x > n || y < 1 || y > n) continue;
            if(x + y > n + 1) break;
            for(auto p : mp1[tx][ty]) {
                mp1[x][y][p.first ^ a[x][y]] += p.second;
            }
            if(!st[x][y]){
                que.push({x, y});
                st[x][y] = true;
            }
        }
    }
}

void bfs2()
{
    queue<pii> que;
    que.push({n, n});
    st[n][n] = true;
    while(que.size()) {
        auto t = que.front();
        int tx = t.first, ty = t.second;
        que.pop();
        for(int i = 0; i < 2; i ++) {
            int x = tx - dx[i], y = ty - dy[i];
            if(x < 1 || x > n || y < 1 || y > n) continue;
            if(x + y <= n + 1) break;
            for(auto p : mp2[tx][ty]) {
                mp2[x][y][p.first ^ a[x][y]] += p.second;
            }
            if(!st[x][y]){
                que.push({x, y});
                st[x][y] = true;
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            scanf("%d", &a[i][j]);
        }
    }
    mp1[1][1][a[1][1]] = 1, mp2[n][n][a[n][n]] = 1;
    bfs1();
    bfs2();
    ll ans = 0;
    for(int i = 1; i <= n; i ++) {
        int r = i, c = n + 1 - i;
        if(r + 1 <= n) {
            for(auto p : mp1[r][c]) {
                ans += mp2[r + 1][c][p.first ^ 0] * p.second;
            }
        }
        if(c + 1 <= n) {
            for(auto p : mp1[r][c]) {
                ans += mp2[r][c + 1][p.first ^ 0] * p.second;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}