XOR Paths

从左上角走到右下角，一共 $C=n+m-2$ 步，其中选 $m-1$ 步向右走，剩下 $n-1$ 步向下走。直接生成所有的向右走的步骤的子集，最多有 $n^{38}$ 种，太多了。我们使用meet-in-the-middle来优化：把要走的路，分成两段，前 $\frac{C}{2}$ 步和后 $C-\frac{C}{2}$ 步，第一段中间选 $x$ 步向右，则第二段中间选 $m-x-1$ 步向右。分别生成每步的所有子集，将这段路的XOR值、 $x$ （向右走的步数）存下来，就可以了。

我们使用map来保存走到同一个位置、以及XOR值一样的方案{XOR,x}的数量，然后对于每一个前一半路的记录，查询后一半结果中{XOR ^ k, m-1-x}的方案数量，乘起来累加就可以了。注意后一半要包含走到右下角点的最后一步。

一个bitmask中1的位数，可以使用__builtin_popcount()来统计（long long的话，就是__builtin_popcountll()）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n,m;
ll K;
ll a[25][25];
map<pair<ll,int>,ll> ml, mr;    // results for top-left and bottom-right halves
                                // {{xor_result, horizontal_count}, # of paths}
int main() {
    scanf("%d %d %lld", &n, &m, &K);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%lld", &a[i][j]);
    
    int C = n+m-2;
    // left half
    for (int bm = 0; bm < (1 << C/2); bm++) {
        int pc = __builtin_popcount(bm);
        if (pc > m) continue;
        int r = 0, c = 0;
        ll res = 0;
        for (int i = 0; i < C/2; i++) {
            res ^= a[r][c];
            if (bm & (1 << i))
                c++;
            else
                r++;
        }
        ml[{res,pc}]++;
    }
    // right half
    for (int bm = 0; bm < (1 << (C-C/2)); bm++) {
        int pc = __builtin_popcount(bm);
        if (pc > m) continue;
        int r = n-1-(C-C/2-pc), c = m-1-pc;
        ll res = 0;
        for (int i = 0; i < C-C/2; i++) {
            res ^= a[r][c];
            if (bm & (1<<i)) c++; else r++;
        }
        res ^= a[n-1][m-1];
        mr[{res,pc}]++;
    }
 
    ll ans = 0;
    // meet in the middle
    for (auto e: ml) {
        ll x = e.first.first ^ K;
        int hori = m-1-e.first.second;
        ans += e.second * mr[{x,hori}];
    }
    printf("%lld", ans);
    return 0;
}