题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int a[N],dp[N][N][N];
int dfs(int pos,int cnt0,int cnt1,int limit,int lead){//两个cnt参数记录0和1出现的次数
if(!pos) return cnt0>=cnt1;
if(!lead&&!limit&&dp[pos][cnt0][cnt1]!=-1) return dp[pos][cnt0][cnt1];
int res = 0,up = limit?a[pos]:1;
for(int i = 0;i<=up;i++){
if(lead&&!i) res+=dfs(pos-1,cnt0,cnt1,limit&&i==a[pos],1);
else if(i)res+=dfs(pos-1,cnt0,cnt1+1,limit&&i==a[pos],0);
else res+=dfs(pos-1,cnt0+1,cnt1,limit&&i==a[pos],0);
}
return limit?res:(lead?res:dp[pos][cnt0][cnt1]=res);
}
int calc(int x){
memset(dp,-1,sizeof dp);
int len = 0;
while(x) a[++len] = x&1,x>>=1;
return dfs(len,0,0,1,1);
}
int main(){
int a,b;
cin>>a>>b;
cout<<calc(b)-calc(a-1);
}