题目链接：HDOJ4734

题意：给定整数a，b：先按照题目意思求得F（a），然后求区间【0,b】内有多少个数不超过F（a）


刷了这么久的数位DP，对于这种模型题感觉还是在的

dp【len】【x】：数位为len，不超过j的数的总数量


求F（a）写个函数进行计算就好了

最终的要求是不超过F（a），所以每次用F（a）去减去数位DP枚举的数，如果最终不小于0，说明这个值是可以的

剩下的跟模板就没有区别了


#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

int a,b,digit[20];
int dp[20][100000];

int dfs(int pos,int x,bool flag){
	if (pos==0) return x>=0;
	if (x<0) return 0;
	if (flag&&dp[pos][x]!=-1) return dp[pos][x];
	int ans=0;
	int maxnumber=flag?9:digit[pos];
	for(int i=0;i<=maxnumber;i++)
		ans+=dfs(pos-1,x-i*(1<<(pos-1)),flag||i<maxnumber);
	if (flag) dp[pos][x]=ans;
	return ans;
}

int F(int x){
	int ret=0,len=0;
	while(x){
		ret+=(x%10)*(1<<len);
		len++;
		x/=10;
	}
	return ret;
}

int calc(int a,int b){
	int len=0;
	while(b){
		digit[++len]=b%10;
		b/=10;
	}
	return dfs(len,F(a),0);
}

int main(){
	//input;
	int T;
	scanf("%d",&T);
	memset(dp,-1,sizeof(dp));
	for(int Case=1;Case<=T;Case++){
		scanf("%d%d",&a,&b);
		printf("Case #%d: %d\n",Case,calc(a,b));
	}
	return 0;
}