出题人题解 | #筱玛的迷阵探险#

原题解链接：https://ac.nowcoder.com/discuss/151505

折半搜索。

对对角线上每个结点开一个$TrieTrie$。前 $\lfloor \frac{n}{2}\rfloor \backslash left\backslash lfloor\backslash frac\{n\}\{2\}\backslash right\backslash rfloor$ 步搜出来的答案用$TrieTrie$保存, 后 $n-\lfloor \frac{n}{2}\rfloor n-\backslash left\backslash lfloor\backslash frac\{n\}\{2\}\backslash right\backslash rfloor$ 步的答案在$TrieTrie$上寻找最大值。

时间复杂度 $\mathcal{O}(2^{\frac{n}{2}}\log A)\backslash mathcal\{O\}\backslash left(2^\{\backslash frac\{n\}\{2\}\}\; \backslash log\; A\backslash right)$ 。

#include<bits/stdc++.h>
#define N (1<<20)
using namespace std;
int n,cnt,sta,ans,a[55][55],d[N*16],rt[N],ls[N*16],rs[N*16];
void insert(int &k,int x,int i){
	if (!k) k=++cnt;d[k]++;
	if(i<0)return;
	int op=(x>>i&1);
	if (op) insert(rs[k],x,i-1);
	else insert(ls[k],x,i-1);
}
int query(int k,int x,int i){
	if (!k) return 0;
	int op=(x>>i&1);
	if (op){
		if (d[ls[k]]) return (1<<i)+query(ls[k],x,i-1);
		else return query(rs[k],x,i-1);
	}
	else {
		if (d[rs[k]]) return (1<<i)+query(rs[k],x,i-1);
		else return query(ls[k],x,i-1);
	}
}
void dfs(int x,int y,int sum,int dep){
	if (x>n||y>n) return;
	sum^=a[x][y];
	if (dep==n){
		insert(rt[x],sum,30);
		return;
	}
	dfs(x+1,y,sum,dep+1);
	dfs(x,y+1,sum,dep+1);
}
void dfs1(int x,int y,int sum,int dep){
	if (x<1||y<1) return;
	sum^=a[x][y];
	if (dep==n-1){
		if (x-1) ans=max(ans,query(rt[x-1],sum,30));
		ans=max(ans,query(rt[x],sum,30));
		return;
	}
	dfs1(x-1,y,sum,dep+1);
	dfs1(x,y-1,sum,dep+1);
}
int main(){
	scanf("%d%d",&n,&sta);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);if(n==1)return printf("%d\n",a[1][1]^sta),0;
	dfs(1,1,sta,1);
	dfs1(n,n,0,1);printf("%d\n",ans);
	return 0;
}