链接Miku

数位dp,定义$dp_{i,j,k}$为到了第i位有j个零并且有k个前导零的方案数

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int l,r;
int dp[50][50][50];
int n1[50];
int n2[50];
int p;
int cnt;
int dfs(int pos,int num,int leadz,int li,int numz){
    int ret=0;
    if(pos>p){
        if((!leadz )&&num>=(p-num-numz)) return 1;
        return 0;
    }
    if(dp[pos][num][numz]!=-1&&leadz==0&&li==0){
        return dp[pos][num][numz];
    }
    int lim= (li==1? n1[p-pos+1]:1);
    for(int i=0;i<=lim;++i){
         ret+=dfs(pos+1,num+(i==0&&leadz==0),leadz&&(i==0),li&&i==lim,numz+(leadz&&(i==0)));
    }
    if(leadz==0&&li==0)
    dp[pos][num][numz]=ret;
    return ret;
}
int solve(int x){
     p=0;
    while(x){
        n1[++p]=x%2;
        x/=2;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(1,0,1,1,0);
}
int main(){
    scanf("%d%d",&l,&r);
    cout<<solve(r)-solve(l-1);
    return 0;
}