前导0一定要处理...
//进阶指南dp挺好的,经典又不难...先把最后一题写完吧orz. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int base=33; const int N=33,M=100; ll f[N][M];//到了第i位0与1的差值+base后面填的数没有限制有多少种方案. ll a[N];//存二进制数. ll dfs(int pos,int c,int limit,int is_zero)//到了哪一位,差值是多少,这一位填数有没有限制,前面是不是填了数 { if(pos==0)//递归出口就是pos=0,因为pos=0就填完了. { return c>=base;//假如c>=base就有一种合法解,否则没有呐呐呐. } if(f[pos][c]&&!limit&&!is_zero)//假如这个点记忆化过.且现在填数没有限制. { return f[pos][c];//有限制的填数和没限制的填数方案数是完全不同滴~ } int ans=0; int x; limit?x=a[pos]:x=1;//有限制就是最大填a[pos],没限制随便填1. for(int i=0;i<=x;i++)//枚举这个地方可以填什么. { if(i==0)//假如这个地方填0. { if(is_zero) ans+=dfs(pos-1,base,limit&&(i==a[pos]),1); else ans+=dfs(pos-1,c+1,limit&&(i==a[pos]),0); } else//否则填1. { ans+=dfs(pos-1,c-1,limit&&(i==a[pos]),0); } } if(!limit&&!is_zero)//假如没有限制的话,就直接记忆化一下呐. { f[pos][c]=ans; } return ans; } inline ll solve(int x) { int len=0; memset(a,0,sizeof a); while(x) { a[++len]=(x&1); x>>=1; } return dfs(len,base,1,1); } int main() { ll l,r; cin>>l>>r; cout<<solve(r)-solve(l-1)<<endl; return 0; }