codeforces 1006 F. Xor-Paths (折半搜索+中途相遇法)

    #include <bits/stdc++.h>
    #include <iomanip>
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
    #define pb push_back
    #define mkp(a,b) make_pair(a,b)
    #define fi first
    #define se second
    #define stn(a) setprecision(a)//小数总有效位数
    #define stfl setiosflags(ios::fixed)//点后位数:cout<<stfl<<stn(a);
    using namespace std;
    typedef long long ll;
    const double PI=acos(-1);
    const int inf = 0x3f3f3f3f; //9
    const ll inff = 0x3f3f3f3f3f3f3f3f; //18
    
    int n,m;
    ll k,a[30][30];
    unordered_map<ll,ll>mp[30];
    ll ans=0;
    
    void dfs1(int x,int y,ll now)
    {
    if(x+y==(m+n+2)/2)
    {
        mp[x][now]++;  //因为此时y是唯一的,所以不用记作mp[x][y][sum]
        return;
    }
    if(x<n) dfs1(x+1,y,now^a[x+1][y]);
    if(y<m) dfs1(x,y+1,now^a[x][y+1]);
    }
    
    void dfs2(int x,int y,ll now)
    {
    if(x+y==(m+n+2)/2) //虽然最初的思路是两次dfs分别步数都走一半,但这里不用去管m+n的奇偶,即步数是否缺一步,两次dfs要满足的都是这个等式,从坐标的角度那么此时x,y这两点必定已经重合了,不会出现缺一步的情况
    {
        if(mp[x][now^a[x][y]^k]!=0) //这里now^a[x][y] 是为了退回到x,y的之前那格
            ans+=mp[x][now^a[x][y]^k];
        return;
    }
    if(x>1) dfs2(x-1,y,now^a[x-1][y]);
    if(y>1) dfs2(x,y-1,now^a[x][y-1]);
    }
    
    int main()
    {
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    dfs1(1,1,a[1][1]);
    dfs2(n,m,a[n][m]);
    cout<<ans<<endl;
    }