作为我AC的第100道bzoj题，当然要立个标志辣~~ 分析：这题没那么简单，一开始分析了一波性质，觉得不是dp就是组合数，，结果发现两种做法都有，但是组合数的有点蒙蔽，然后就写了记忆化搜索，然后wa了1w年，只能膜题解。。
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; int f[50][50][50],s[50],l,r,len,ans; inline int dfs(int now,int x1,int x2,bool bz,bool flag) { if(!now) { if (flag)return 1; if (x1>=x2)return 1; return 0; } if (!flag&&!bz&&f[now][x1][x2]!=-1)return f[now][x1][x2]; int last; if (bz)last=s[now]; else last=1; int ans=0; fo(i,0,last) { if (flag) { if (!i)ans+=dfs(now-1,0,0,bz&&last==i,1); else ans+=dfs(now-1,x1,x2+1,bz&&last==i,0); } else { if (!i)ans+=dfs(now-1,x1+1,x2,bz&&last==i,0); else ans+=dfs(now-1,x1,x2+1,bz&&last==i,0); } } if (!bz&&!flag)f[now][x1][x2]=ans; return ans; } inline int get(int n) { len=0; while (n) { s[++len]=n%2; n/=2; } ans=dfs(len,0,0,1,1); return ans; } int main() { while (scanf("%d%d",&l,&r)!=EOF) { memset(f,-1,sizeof(f)); printf("%d\n",get(r)-get(l-1)); } }