「Codeforces 1006F」Xor-Paths

Description

给定一个 $n \times m$ 的网格，每个格子的权值为 $a_{i,j}$，现在要从 $(1,1)$ 走到 $(n,m)$，求异或和等于 $k$ 的路径数。

$(1 \leq n,m \leq 20,0 \leq a_{i,j},k \leq 10^{18})$

Source

[Luogu]CF1006F

[Codeforces]1006F

Solution

$n,m$ 的范围很小，所以考虑搜索。

直接暴搜显然不行，因为路径数很多。

所以使用 折半搜索 。

从起点和终点开始分别搜索，搜到对角线停止，设路径总数为 $k$，则时间复杂度可以降为 $O(\sqrt k)$ 。

起点开始只能向下或向右走，终点开始只能向上或向左走，注意边界。

我们可以开一个 $\rm map$ 存下从 $(1,1)$ 到对角线上的点 $(x,y)$ 异或和为 $val$ 的路径数。第二次搜到 $(x,y)$ 时，若当前异或和为 $val$，则答案需要加上从 $(1,1)$ 到 $(x,y)$ 异或和为 $k \oplus val$ 的路径数（$\oplus$ 表示异或，异或的逆运算也是异或）。

怎么判断 $(x,y)$ 是否在对角线上？只要看 $x+y$ 是否与 $\left \lfloor \frac{n + m}{2} \right \rfloor + 1$ 相等即可（对角线是一次函数）。至于为什么 $+1$，是因为能够防止 $n = m = 1$ 的情况出错。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 20;
int n, m;
LL k, ans, a[MAXN + 5][MAXN + 5];
map<LL, LL> cnt[MAXN + 5];

void dfs1(int x, int y, LL val) {//表示当前到点 (x,y)，路径异或和为 val 
    if (x + y == (n + m) / 2 + 1) {
        ++cnt[x][val];//统计 (1,1) -> (x,y) 异或和为 val 的路径数 
        return;
    }
    if (x < n) dfs1(x + 1, y, val ^ a[x + 1][y]);
    if (y < m) dfs1(x, y + 1, val ^ a[x][y + 1]);
}

void dfs2(int x, int y, LL val) {
    if (x + y == (n + m) / 2 + 1) {//搜到对角线就停止
        ans += cnt[x][k ^ val ^ a[x][y]];
        //这里异或 a[x][y] 是因为第二次到这个点多异或了 (x,y) 一次，
        //而第一次到 (x,y) 时已经异或过了，再异或一次相当于只保留一次异或 
        return;
    }
    if (x > 1) dfs2(x - 1, y, val ^ a[x - 1][y]);
    if (y > 1) dfs2(x, y - 1, val ^ a[x][y - 1]);
}

int main() {
    read(n), read(m), read(k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            read(a[i][j]);
    dfs1(1, 1, a[1][1]), dfs2(n, m, a[n][m]);
    write(ans);
    putchar('\n');
    return 0;
}