题目描述

blablabla

样例

blablabla

算法

dfs记忆化搜索即可.难点在于一定要处理前导0…不然会错的,有限制的填数和无限制的填数dp值也是不一样的~限制的意思就是比如原数是101,你在最高位填了0,后面0/1随便填,而你填1了,那么后面就只能填比它小的数…
具体代码有很多注释.

(数位dp) $O(=-=)$

blablabla

时间复杂度

参考文献

C++ 代码

//进阶指南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;
}