求调
查看原帖
求调
1099150
xrtbclx楼主2025/2/8 11:36
#include<bits/stdc++.h>
#define int long long
using namespace std;

int cnt,num[45];
int dp[45][45][45];
int dfs(bool uflg,bool zflg,int pos,int sum0,int sum1)
{
	if(pos < 0)return sum0 >= sum1;
	if(!uflg && !zflg && dp[pos][sum0][sum1] != -1)return dp[pos][sum0][sum1];
	int t = uflg ? num[pos] : 1;
	int ans = 0;
	for(int i = 0; i <= t; i++)
	{
		if(zflg)ans += dfs(uflg && i == t,zflg && i == 0,pos-1,sum0 + (i==0),sum1 + (i==1));
		else
		{
			ans += dfs(uflg && i == t,zflg,pos-1,sum0 + (i==0),sum1 + (i==1));
		}
	}
	if(!uflg && !zflg) dp[pos][sum0][sum1] = ans;
	return ans;
} 
int d(int x)
{
	memset(num,0,sizeof(num));
	memset(dp,-1,sizeof(dp));
	cnt = 0;
	cnt++;
	while(x)
	{
		num[cnt++] = x % 2;
		x /= 2;
	}
	return dfs(1,1,cnt-1,0,0);
}
signed main()
{
    int a,b;
    cin >>a>>b;
    cout <<d(b)-d(a-1);
}
2025/2/8 11:36
加载中...