题解 [ABC271F] XOR on Grid Path

翼德天尊 · 2022-11-04 07:33:24 · 题解

数据范围太小，但是如果暴力的话， O(2^{2n}) 的复杂度又太高，稍微有点接受不了。

于是考虑异或的一个性质，如果路径异或和为 0，则随意找一个切线切开路径就可以得到两条异或和相同的路径。

所以我们可以考虑一个叫作 meet in the middle 的 trick，将网格从右上到左下斜着切开，分别对于左上和右下到对角线作一遍 dfs。

具体来说，我们可以对于这条对角线的每一个方格开一个 map，将左上走到方格 p 的所有路径的异或和都存在方格 p 的 map 里。

从右下到左上搜的时候只需要从 map 中进行查询即可。

时间复杂度 O(n2^n\log 2^n)，常数好像不大。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=24;
int n,a[N][N];
ll ans;
map<int,int> ma[N];
ll read(){
    ll w=0,f=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w*f;
}
void dfs1(int x,int y,int now){
    if (x+y==n){
        ma[x][now]++;
        return;
    }
    dfs1(x+1,y,now^a[x+1][y]);
    dfs1(x,y+1,now^a[x][y+1]);
}
void dfs2(int x,int y,int now){
    if (x+y==n){
        ans+=ma[x][now];
        return;
    }
    dfs2(x-1,y,now^a[x][y]);
    dfs2(x,y-1,now^a[x][y]);
}
int main(){
    n=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            a[i][j]=read();
    dfs1(1,1,a[1][1]);
    dfs2(n,n,0);
    cout<<ans<<"\n";
    return 0;
}