求一个区间内的数含有多少个0.
dp[len][pre]表示长度为len的数,含有pre个0.
需要加一个标记,来表示前缀是否为0(可以是一串连续的0),如果前缀一直为0,就一直搜,如果前缀不为0,就可以用到dp[len-1][pre+1]或者dp[len-1][pre]
了,如果前缀的最后一位是0,就是dp[len-1][pre+1],如果前缀的最后一位不是0,就是dp[len-1][pre],当然了第一次肯定是需要先搜的.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define maxn 30
LL dp[maxn][maxn];//代表长度为len的数字,有多少个0
LL digit[maxn];
int LEN;
LL dfs(int len,LL pre,int flag,bool fp) //dfs版本的纯属暴力枚举每一个数字,而递推版本的是考虑了前缀的影响
{
if(len==)
{
if(flag)
return ;
else
return pre;
}
if(!fp && dp[len][pre] != - && !flag) //如果之前的数字不全是0,可以直接用
{
return dp[len][pre];
}
LL ret =;
int fpmax = fp ? digit[len] : ;
for(int i=;i<=fpmax;i++) //分别算出以i开头的数的方案数,
{
LL temp=;
if(flag) //如果之前一直是0
{
temp=dfs(len-,pre,flag && (i==),fp && i==fpmax);
ret+=temp;
}
else
{
if(i==)
{
temp=dfs(len-,pre+,flag,fp && i==fpmax);
ret+=temp;
}
else
{
temp=dfs(len-,pre,flag,fp && i==fpmax);
ret+=temp;
}
}
}
if(!fp && !flag) //如果之前的数字不全是0
dp[len][pre]= ret;
return ret;
} LL f(LL n)
{
if(n==-)
return ;
int len=;
while(n)
{
digit[++len] = n % ;
n /= ;
}
LL ans=;
// LEN=len;
ans+=dfs(len,,,true);
return ans;
}
void init()
{
memset(dp,-,sizeof(dp));
}
int main()
{
//freopen("test.txt","r",stdin);
int t;
scanf("%d",&t);
int Case=;
while(t--)
{
init();
LL n,m;
scanf("%lld%lld",&n,&m);
LL ans1=f(m);
// printf("%lld\n",ans1);
init();
LL ans2=f(n-);
// printf("%lld\n",ans2);
printf("Case %d: %lld\n",++Case,ans1-ans2);
}
return ;
}