题解 CF1006F 【Xor-Paths】

jdsb · 2020-05-15 15:44:34 · 题解

题意

给出一个矩阵，求出从左上角到右下角所经过的点的点权异或和为k的路径数

分析

首先我们发现n，m的范围很小，只有20，所以可以考虑搜索，开一个map数组s[i][j][k]，表示走到(i,j)时，异或和为k的路径数，但是此时的时间复杂度为2^{40}，会发现还是要T，所以我们就要优化。考虑双向搜索，以对角线为界限，第一个dfs记录从左上角到对角线的方案，第二个dfs从右下角出发，每当走到对角线时就累计答案，这时时间复杂度就能优化到2^{20}。这样就不会T了。一些细节在代码里有说明。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
ll k,a[25][25],ans;
map<ll,ll> s[25][25];
void dfs1(int x,int y,ll sum)
{
    if(x>n||y>m) return;
    //以(n+m)/2+1为对角线，到达这里时就退出 
    if(x+y==(n+m)/2+1)
    {
        ++s[x][y][sum];
        return;
    }
    dfs1(x+1,y,a[x+1][y]^sum);
    dfs1(x,y+1,a[x][y+1]^sum);
    //只向下边和右边走 
}
void dfs2(int x,int y,ll sum)
{
    if(x<1||y<1) return;
    if(x+y==(n+m)/2+1)
    {
        ans+=s[x][y][sum^k^a[x][y]];
        /*一个小技巧，一个数异或两次等于没异或，从头到(x,y)
        和从尾到(x,y)都异或了一次，在异或一次才算异或过它*/ 
        return;
    }
    dfs2(x-1,y,a[x-1][y]^sum);
    dfs2(x,y-1,a[x][y-1]^sum);
    //反向dfs，只向上边和左边走 
}
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]);
    dfs1(1,1,a[1][1]);
    dfs2(n,m,a[n][m]);
    printf("%lld",ans);
    return 0;
}