题解 CF1006F 【Xor-Paths】
VenusM1nT
·
·
题解
大水题一道。首先考虑直接爆搜，肯定会超时不用想，复杂度高达 $2^{40}$，但是如果对其折半的话，就是 $2\times2^{20}$ 的复杂度，这个是完全可以接受的，所以我们矩阵折半，从 右上-左下 对角线分开，先搜左上这一块，把搜出的异或和记录在 $\texttt{map}$ 里，再搜右下角，假如我们搜出的异或和为 $\text{cnt}$，那么我们只需要找一下 $\texttt{map}$ 里有多少个 $\text{k xor cnt}$ 与之对应即可。
```cpp
#include<bits/stdc++.h>
#define MAXN 25
#define reg register
#define inl inline
#define int long long
using namespace std;
map <int,int> mp[MAXN][MAXN];
int n,m,k,a[MAXN][MAXN],lim,ans;
void Dfs1(reg int x,reg int y,reg int cnt)
{
if(x<1 || x>n || y<1 || y>m) return;
cnt^=a[x][y];
if(x+y==lim)
{
mp[x][y][cnt]++;
return;
}
Dfs1(x+1,y,cnt);
Dfs1(x,y+1,cnt);
}
void Dfs2(reg int x,reg int y,reg int cnt)
{
if(x<1 || x>n || y<1 || y>m) return;
if(x+y==lim)
{
ans+=mp[x][y][cnt^k];
return;
}
cnt^=a[x][y];
Dfs2(x-1,y,cnt);
Dfs2(x,y-1,cnt);
}
signed main()
{
scanf("%lld %lld %lld",&n,&m,&k);
for(reg int i=1;i<=n;i++)
{
for(reg int j=1;j<=m;j++) scanf("%lld",&a[i][j]);
}
lim=(n+m+2)/2;
Dfs1(1,1,0);
Dfs2(n,m,0);
printf("%lld\n",ans);
return 0;
}
```