首页 > > 程序设计 > C/C++ >

Codeforces#498F. Xor-Paths(折半搜索)

2018-07-18 01:15:21来源：博客园阅读 ()

There is a rectangular grid of size $n \times m$

You can move to the right or to the bottom only. Formally, from the cell ( $i, j$
The xor of all the numbers on the path from the cell ( $1, 1$

Find the number of such paths in the given grid.

Input

The first line of the input contains three integers $n$

The next $n$

Output

Print one integer — the number of paths from ( $1, 1$

Examples

input

Copy

output

Copy

input

Copy

output

Copy

input

Copy

3 4 1000000000000000000
1 3 3 3
0 3 3 2
3 0 1 1

output

Copy

Note

All the paths from the first example:

$(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3)$
$(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (3, 3)$
$(1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3)$

All the paths from the second example:

$(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3) \to (3, 4)$
$(1, 1) \to (2, 1) \to (2, 2) \to (3, 2) \to (3, 3) \to (3, 4)$
$(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (2, 4) \to (3, 4)$
$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3) \to (3, 4)$
$(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (3, 3) \to (3, 4)$

题意：从$(1, 1)$走到$(n, m)$，路径上权值异或起来为$k$的有几条

昨晚前五题都1A之后有点上天qwq。。想了很久才发现这是个思博题不过没时间写了qwq。

考虑如果直接dfs的话是$2^{n + m}$

然后meet in the middle 一下就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#define MP(x, y) make_pair(x, y)
#define Pair pair<int, int> 
#define int long long 
using namespace std;
const int MAXN  = 2 * 1e5 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, K;
int a[21][21];
cc_hash_table<int, int> mp[21];
int dfs(int x, int y, int now) {
    if(x < 1 || x > N || y < 1 || y > M) return 0;
    if(x + y == (N + M + 2) / 2) return mp[x][now ^ a[x][y]];
    int ans = 0;
    ans += dfs(x - 1, y, now ^ a[x - 1][y]);
    ans += dfs(x, y - 1, now ^ a[x][y - 1]);
    return ans;
}
void fuck(int x, int y, int now) {
    if(x < 1 || x > N || y < 1 || y > M) return ;
    if(x + y == (N + M + 2) / 2) {mp[x][now]++; return ;}
    fuck(x + 1, y, now ^ a[x + 1][y]);
    fuck(x, y + 1, now ^ a[x][y + 1]);
}
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    N = read(); M = read(); K = read();
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            a[i][j] = read();
    fuck(1, 1, a[1][1]);
    printf("%lld", dfs(N, M, K ^ a[N][M]));
}
/*
1 1 1000000000000000000
1000000000000000000
*/