Codeforces Round #498 (Div. 3)--F. Xor-Paths

F. Xor-Paths

There is a rectangular grid of size n×mn×m . Each cell has a number written on it; the number on the cell (i,ji,j ) is ai,jai,j . Your task is to calculate the number of paths from the upper-left cell (1,11,1 ) to the bottom-right cell (n,mn,m ) meeting the following constraints:

• You can move to the right or to the bottom only. Formally, from the cell (i,ji,j ) you may move to the cell (i,j+1i,j+1 ) or to the cell (i+1,ji+1,j ). The target cell can't be outside of the grid.
• The xor of all the numbers on the path from the cell (1,11,1 ) to the cell (n,mn,m ) must be equal to kk (xor operation is the bitwise exclusive OR, it is represented as '^' in Java or C++ and "xor" in Pascal).

Find the number of such paths in the given grid.

Input

The first line of the input contains three integers nn , mm and kk (1≤n,m≤201≤n,m≤20 , 0≤k≤10180≤k≤1018 ) — the height and the width of the grid, and the number kk .

The next nn lines contain mm integers each, the jj -th element in the ii -th line is ai,jai,j (0≤ai,j≤10180≤ai,j≤1018 ).

Output

Print one integer — the number of paths from (1,11,1 ) to (n,mn,m ) with xor sum equal to kk .

题意：在一个n*m的网格上移动，只能向下或向右移动。在移动过程中每个网格上的值要异或起来，此值是k，则答案++。

做法：因为n*m的状态太多，所以分成两半，分别dfs。用map存所有路径到这个方格的异或值的路径数。这方法之前在省赛中也遇到过，但还是想不到，看了大佬的代码才知道。

---

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<time.h>
#include<set>
#include<bitset>
#include<cstring>
#define inf 0x3f3f3f3f//3f3f3f3f
#define lowbit(a) ((a)&(-(a)))
typedef long long ll;
using namespace std;
typedef long long ll;
ll ans;
map<ll,int >mp[30][30];
int n,m;
ll k,a[30][30];
void dfs(int x,int y,int t,ll now)
{
    if(t==0)
    {
        mp[x][y][now]++;
        return ;
    }
    if(x+1<=n)dfs(x+1,y,t-1,now^a[x][y]);
    if(y+1<=m)dfs(x,y+1,t-1,now^a[x][y]);
}
void dfs1(int x,int y,int t,ll now)
{
    if(t==0)
    {
        ans+=mp[x][y][now];
        return ;
    }
    if(x-1>0)dfs1(x-1,y,t-1,now^a[x-1][y]);
    if(y-1>0)dfs1(x,y-1,t-1,now^a[x][y-1]);
}
int main()
{

    scanf("%d%d%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&a[i][j]);
        }
    }
    int t=n+m-2;
    dfs(1,1,t/2,0);
    dfs1(n,m,t-t/2,k^a[n][m]);
    printf("%lld",ans);
    return 0;
}

这方法真的是很妙，瞬间降低了一个平方的复杂度，以后做题希望可以用到。