Round Numbers(数位dp)

此题新颖之处在于二进制的数位dp，平常见的都是十进制数位dp
因为要统计0的数量，所以前导零会有影响，
那么当dp也只在没有前导零的时候才记忆化。
抄自洛谷：
由于我们要搜的数可能很长，所以我们的直接最高位搜起

举个例子：假如我们要从 [0,1000] 找任意相邻两数相等的数

显然 111,222,888 等等是符合题意的数

但是我们发现右端点 1000 是四位数

因此我们搜索的起点是 0000 ，而三位数的记录都是 0111,0222,0888 等等

而这种情况下如果我们直接找相邻位相等则 0000 符合题意而 0111,0222,0888 都不符合题意了

所以我们要加一个前导0标记

如果当前位 lead=1 而且当前位也是0，那么当前位也是前导0， pos+1 继续搜；
如果当前位 lead=1 但当前位不是0，则本位作为当前数的最高位， pos+1 继续搜；（注意这次根据题意st或其他参数可能发生变化）

#include<bits/stdc++.h>
using namespace std;
int a[32];
int dp[32][64];//0-1,base=32
int dfs(int pos,int sta,bool limit,bool lead)
{
    if(pos==-1) return sta>=32;
    if(!lead && !limit && dp[pos][sta]!=-1) return dp[pos][sta];
    int res=0;
    for(int i=0;i<=(limit?a[pos]:1);++i)
    {
        if(lead && i==0) res+=dfs(pos-1,sta,limit&&i==a[pos],lead);
        else res+=dfs(pos-1,sta+(i==0?1:-1),limit&&i==a[pos],lead&&i==0);
    } 
    if(!lead && !limit) dp[pos][sta]=res;
    return res;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x&1;
        x>>=1;
    }
    return dfs(pos-1,32,true,true);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    int le,ri;
    while(~scanf("%d%d",&le,&ri))
    {
        printf("%d\n",solve(ri)-solve(le-1));
    }
    return 0;
}