CF#498 1006F Xor-Paths

题意：一个n * m的矩阵，求从左上走到右下经过的数异或和为k的方案数。

题解：

　　因为数据范围较小，所以我们可以采用meet in the middle过掉此题、、、

　　然而define inf LL 才过。。。。

#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 22
#define LL long long
#define int LL

int n, m;
LL k, ans;
LL s[AC][AC];

map<int, LL> Map[AC];

inline LL read()
{
    LL x = 0;char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10ll + c - '0', c = getchar();
    return x;
}

void pre()
{
    n = read(), m = read(), k = read();
    for(R i = 1; i <= n; i ++)
        for(R j = 1; j <= m; j ++) s[i][j] = read();
}

void dfs1(int x, int y, LL now)//从左上角开始往对角线搜
{
    if(x < 1 || x > n || y < 1 || y > m) return ;
    if(x + y == (n + m + 2) / 2) {++ Map[x][now]; return;}
    dfs1(x + 1, y, now ^ s[x + 1][y]);
    dfs1(x, y + 1, now ^ s[x][y + 1]);
}

void dfs2(int x, int y, LL now)//从右下角开始往对角线搜
{
    if(x < 1 || x > n || y < 1 || y > m) return ;
    if(x + y == (n + m + 2) / 2) {ans += Map[x][now ^ s[x][y]]; return ;}//不能把同一个数异或2次。
    dfs2(x - 1, y, now ^ s[x - 1][y]);
    dfs2(x, y - 1, now ^ s[x][y - 1]);
}

signed main()
{
    freopen("in.in", "r", stdin);
    pre();
    dfs1(1, 1, s[1][1]);
    dfs2(n, m, k ^ s[n][m]);//因为x ^ y = k ----> x ^ k = y
    printf("%lld
", ans);
    fclose(stdin);
    return 0;
}