meet in the middle，也可以叫折半搜索，是一种用来优化爆搜的方式。
适用于一些数据范围比较小可以爆搜——但还没有小到可以直接搜的程度。可以让复杂度从 \(O(a^b)\) 降到 \(O(a^{b/2})\)
适用的题目一般与异或有关（才能拆成两半搜）。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=40;
int n,m;
int ansn=0x3f3f3f3f;
ll all,vis[N];
map<ll,int> ans;
void dfs(int l,int r,int now,int tot){
if(ans[now]) ans[now]=min(ans[now],tot);
else ans[now]=tot;
if(ans[now^all]||now==all) ansn=min(ansn,ans[now^all]+tot);
if(l>r) return;
dfs(l+1,r,now,tot);
dfs(l+1,r,now^vis[l],tot+1);
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
vis[x]^=1<<y;
vis[y]^=1<<x;
}
for(int i=1;i<=n;i++){
all^=1<<i;
vis[i]^=1<<i;
}
dfs(1,n/2,0,0);
dfs(n/2+1,n,0,0);
printf("%d",ansn);
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=22;
int n;
ll ans;
ll a[N][N];
map<ll,int> cnt[N][N];
void dfs1(int x,int y,ll now){
now^=a[x][y];
if(x+y==n+1){
cnt[x][y][now]++;
return;
}
dfs1(x+1,y,now);
dfs1(x,y+1,now);
}
void dfs2(int x,int y,ll now){
if(x+y==n+1){
ans+=cnt[x][y][now];
return;
}
now^=a[x][y];
dfs2(x-1,y,now);
dfs2(x,y-1,now);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
dfs1(1,1,0);
dfs2(n,n,0);
printf("%lld",ans);
return 0;
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=25;
int n,m;
ll k,cnt;
ll a[N][N];
map<ll,int> ans[N][N];
void dfs1(int x,int y,ll now){
now^=a[x][y];
if(x+y==(n+m)/2+1){
ans[x][y][now]++;
return;
}
dfs1(x,y+1,now);
dfs1(x+1,y,now);
}
void dfs2(int x,int y,ll now){
if(x<0||y<0) return;
if(x+y==(n+m)/2+1){
cnt+=ans[x][y][k^now];
return;
}
now^=a[x][y];
dfs2(x-1,y,now);
dfs2(x,y-1,now);
}
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,0);
dfs2(n,m,0);
printf("%lld",cnt);
return 0;
}