C.数字匹配

如果一个数对 $(x(x$ , $y)y)$ 存在重合位数大于 $kk$ 的子串，那么在所有 $(x>>a(x>>a$ , $y>>b)y>>b)$ 中，一定存在从第 $11$ 位到第 $kk$ 位相互匹配的数对。

令 $maskmask$ 为拥有恰好 $kk$ 个 $11$ 的二进制串，那么 $(x(x$ , $y)y)$ 从第 $11$ 位到第 $kk$ 位相互匹配即可视作 。

于是我们可以设计一个算法：对 $(x(x$ , $y)y)$ 尝试用上述过程匹配，如果失败则尝试对 $(x>>1(x>>1$ , $y)y)$ 和 $(x(x$ , $y>>1)y>>1)$ 匹配，直到某个数的长度小于 $kk$。

这么做显然会 TLE，但我们可以用记忆化搜索优化，把已计算的结果存储下来。

时空复杂度 $O(n^2)O(n^2)$，然而记搜常数巨大，跑得不见得比 $O(n^{2}logn)O(n^2logn)$快。

#include <bits/stdc++.h>
using namespace std;
#define b(x) (1<<((x)-1))

int i,j,n,m,t,res,f[2050][2050],msk;

int dfs(int x,int y){
	if(b(m)>x||b(m)>y)return 0;
	if(~f[x][y])return f[x][y];
	if(((x&msk)==(y&msk))) return f[x][y]=1;
	else return f[x][y]=(dfs(x>>1,y)|dfs(x,y>>1));
}

int main() {
	memset(f,-1,sizeof(f));
	cin>>n>>m;
	msk=b(m+1)-1;
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			res+=dfs(i,j);
		}
	}
	cout<<res;
}