POJ 3252 Round Numbers(数位dp+前导零)

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 35
#define ll long long
using namespace std;
int a[maxn];
ll dp[maxn][maxn][maxn];

ll dfs(int pos, int n0, int n1, bool lead, bool limit){
	if(pos == -1){
		if(n0 >= n1) return 1;
		else return 0;
	}
	if(!limit && !lead && dp[pos][n0][n1] != -1) return dp[pos][n0][n1];
	int up = limit ? a[pos] : 1;
	ll ans = 0;
	for(int i=0;i<=up;i++){
		if(lead && i == 0) ans += dfs(pos - 1, 0, 0, true, limit && i == up);
		else{
			if(i == 0) ans += dfs(pos - 1, n0 + 1, n1, false, limit && i == up);
			else ans += dfs(pos - 1, n0, n1 + 1, false, limit && i == up);
		}
	}
	if(!limit && !lead) dp[pos][n0][n1] = ans;
	return ans;
}

ll solve(ll x){
	int pos = 0;
	while(x){
		a[pos ++] = x & 1;
		x >>= 1;
	}
	return dfs(pos - 1, 0, 0, true, true);
}

int main()
{
	ll l,r;
	scanf("%lld%lld",&l,&r);
	memset(dp, -1, sizeof(dp));
	printf("%lld\n", solve(r) - solve(l - 1));
	return 0;
}