题目大意：给你一个区间$[l,r]$，求在该区间内有多少整数在二进制下$0$的数量$≥1$的数量。数据范围$1≤l,r≤2*10^{9}$。
第一次用记忆化dfs写数位dp，感觉神清气爽~（原谅我这个蒟蒻，原先写的四不像数位dp至少需2h，用真记忆化dfs不到半小时写出）
我们用$f[i][j]$表示在最后的$i+j$为中，用了$i$个$0$，$j$个$1$的方案数（第$i+j$位也可以是$0$）。该方程转移显然为$f[i][j]=f[i-1][j]+f[i][j-1]$。
于是我们用记忆化dfs去求答案，$dfs(n,op,x,y)$表示你构造到从后往前数第$n$位，是否有压着上限，$0$的数量，$1$的数量。
若无压着上限，则答案显然为$dfs(n-1,op,x,y-1)+dfs(n-1,op,x-1,y)$。
若压着上限且第$num[n]$位为$0$，则答案为$dfs(n-1,op,x-1,y)$。 否则答案为$dfs(n-1,op,x,y-1)+dfs(n-1,op^1,x-1,y)$。
搜索时用记忆化加速即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define L int
#define M 50
using namespace std;
L f[M][M]={};//前i+j位中，用了i个0，j个1的方案数
int num[M]={},cnt=;
L dfs(int n,bool op,int x,int y){//当前处理到第n位，且第cnt位到第n+1为已经确定，第n-1位是否压着上限，计划用x个0,和y个1。
if(x==-||y==-) return ;
if(!op&&f[x][y]!=-) return f[x][y];
if(!op){
f[x][y]=dfs(n-,op,x-,y)+dfs(n-,op,x,y-);
return f[x][y];
}
if(!num[n]) return dfs(n-,op,x-,y);
return dfs(n-,,x-,y)+dfs(n-,op,x,y-);
}
L get(L x){
if(x==) return ;
memset(num,,sizeof(num)); cnt=;
int b[]={};
while(x){
num[++cnt]=x&;
b[x&]++; x>>=;
}
L sum=;
if(b[]>=b[]) sum++;
for(int i=;i<=cnt;i++){
for(int j=;j*<=i;j++)
sum+=dfs(i-,i==cnt,i-j,j-);
}
return sum;
}
int main(){
L a,b;
while(cin>>a>>b){
memset(f,-,sizeof(f));
for(int i=;i<M;i++) f[][i]=f[i][]=;
printf("%d\n",get(b)-get(a-));
} }