本文共 1875 字，大约阅读时间需要 6 分钟。

若$(x,y)$满足$x\&y=0$那么可以被计算贡献

贡献为二进制位的最高位的位数

那么容易想到定义$f[i][j][0/1][0/1]$表示枚举到第$i$位,最高位二进制$1$是$j$位置

$x$卡不卡上界,$y$卡不卡上界

这样乍一看是非常优秀的复杂度,然而实际上算一下发现极限数据是

$30^2\ast 2^2\ast 10^5=3.6\ast 10^8$

而且数位$dp$的复杂度是带常数的,会被卡死

所以需要优化

发现当我们在第$x$位放置了$1$,那么其实没必要枚举下去,我们只需要知道接下来有多少种方法填数就好了!!!

所以定义$f[i][0/1][0/1]$表示枚举到二进制第$i$位,$x,y$卡不卡上界的数对方案

我们就可以枚举最高位的$1$在哪里,然后从那个位置开始数位$dp$

复杂度变成$30\ast 2^2\ast 10^5=1.2\ast 10^7$

由于变成了$k$次$dfs$,常数略大,但因为状态固定,所以大部分时间是直接返回的

#include
   
    using namespace std;const int mod = 1e9+7;int t,x,y,a[33],b[33];int f[33][2][2];int dfs(int l,int lim1,int lim2)//h1表示最高位1的位置,h2表示是否有低位1 {
   	if( f[l][lim1][lim2]!=-1 )	return f[l][lim1][lim2];	if( l==0 )	return f[l][lim1][lim2] = 1;	int ed1 = lim1?a[l]:1, ed2 = lim2?b[l]:1;	long long ans = 0;	for(int i=0;i<=ed1;i++)	for(int j=0;j<=ed2;j++)		{
   		if( (i&j)!=0 )	continue;		ans += dfs(l-1,lim1&&(i==ed1),lim2&&(j==ed2) );			}	return f[l][lim1][lim2] = ans%mod;}//f[i][0/1][0/1]表示最高位1在i位置,当前卡不卡上界 int solve(int x,int y){
   	for(int i=1;i<=a[0];i++)	a[i] = 0;	for(int i=1;i<=b[0];i++)	b[i] = 0;	a[0] = b[0] = 0;	while( x ){
    a[++a[0]] = x&1; x>>=1; }	while( y ){
    b[++b[0]] = y&1; y>>=1; }	int mx = max( a[0],b[0] );	for(int i=0;i<=mx;i++)		f[i][0][0] = f[i][0][1] = f[i][1][0] = f[i][1][1] = -1; 	long long ans = 0;	for(int i=1;i<=a[0];i++)//枚举最高位,x是1,y是0		ans += 1ll*dfs( i-1,i==a[0],i>b[0] )*i;	for(int i=1;i<=b[0];i++)//枚举次高位,x是0,y是1 		ans += 1ll*dfs( i-1,i>a[0],i==b[0] )*i;	return ans%mod;}signed main(){
   	cin >> t;	while( t-- )	{
   		scanf("%d%d",&x,&y);		printf("%d\n",solve(x,y) );	}}
   

当然,更好的写法是直接一遍$dfs$统计答案

虽然复杂度完全没区别,但是要简短一点点

比如这里写的

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116673103 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！