给出一段区间a-b，统计这个区间内0-9出现的次数。
比如 10-19，1出现11次（10,11,12,13,14,15,16,17,18,19,其中11包括2个1)，其余数字各出现1次。
Input
两个数a,b（1 <= a <= b <= 10^18)
Output
输出共10行，分别是0-9出现的次数
Input示例
10 19
Output示例
1 11 1 1 1 1 1 1 1 1
思路：用记忆化搜索做，当计算0的数量是要特别注意
代码
#include<stdio.h>
#include<string.h>
#define ll long long
ll dis[12];//记录位数
ll lg,len;
ll s[25];//表示10的i次方
ll ans1[12];//记录答案
ll dp[25][15][2];
ll check(ll a){ //计算分解后的前a位的值
ll i=0;
ll ans=0;
for(i=0;i<=a;i++)
ans+=dis[i]*s[i];
return ans;
}
ll dfs(ll pos,ll lg,ll k){//计算1---9的数量
if(pos<0)
return 0;
ll num=lg?dis[pos]:9;
if(!lg&&dp[pos][k][lg]!=-1)//只有没有限制的时候才能用记忆化记录的结果
return dp[pos][k][lg];
ll i,j;
ll ans=0;
for(i=0;i<=num;i++){
if(i==k){//当i等于k时，当前有k的数量就要加上后面所有可能的数字的个数 （假设是542123，当前面已经遍历完542这三位时，
//当遍历到第四位且第四位为1时，1的数量就等于23中1数量+23）
if(lg&&i==num)//注意，前面的限制不一定能对后面的计算产生影响，要看当前的i是否可以继续产生限制。
ans=ans+check(pos-1)+1+dfs(pos-1,lg&&(i==num),k);//假设是542123这个数字，当取后三位是，一共有123+1种情况（0---123）
else
ans=ans+s[pos]+dfs(pos-1,lg&&(i==num),k);// 假设是542123，当前面已经遍历到541这三位时，
//当遍历到第四位且第四位为1时，1的数量就等于100中1数量+100）
}
else
ans+=dfs(pos-1,lg&&(i==num),k);
}
if(!lg)
dp[pos][k][lg]=ans;
return ans;
}
ll dfs1(ll pos,ll lg,ll lg1){//计算零的数量
if(pos<0)
return 0;
if(!lg&&!lg1&&dp[pos][0][lg]!=-1)//只有当没有限制并且前面有非零数字时，才能用到记忆化保存的数据
{
return dp[pos][0][lg];
}
ll num=lg?dis[pos]:9;
ll i,j;
ll ans=0;
//printf("%d
",num);
//printf("pos=%d
",dis[pos]);
for(i=0;i<=num;i++){
//prllf("c=%d %d
",pos,i);
if(!lg1&&i==0){
if(lg&&i==num)//注意，前面的限制不一定能对后面的计算产生影响，要看当前的i是否可以继续产生限制，在这里连续卡了几次，以为自己考虑了，但是还是没有考虑，以后做题一定要注意。
{
//printf("a=%d %d %d
",pos,i,cal(pos)+1);
ans+=check(pos-1)+1;//同上
}
else
{
ans+=s[pos];
//printf("b=%d
",s[pos]);
}
}
//printf("%d %d %d
",pos,i,ans);
ans+=dfs1(pos-1,lg&&(i==num),lg1&&(i==0));
}
if(!lg&&!lg1)//记忆化没有限制并且前面有非零数字的情况
dp[pos][0][lg]=ans;
return ans;
}
int main(){
ll n,m;
len=0;
scanf("%lld%lld",&n,&m);
ll i;
s[0]=1;
for(i=1;i<=18;i++)
s[i]=s[i-1]*10;
n=n-1;
while(n){//分解数字
dis[len++]=n%10;
n=n/10;
}
memset(dp,-1,sizeof(dp));
ans1[0]=-dfs1(len-1,1,1);
//printf("%d
",ans1[0]);
for(i=1;i<=9;i++){
ans1[i]=-dfs(len-1,1,i);
}
len=0;
while(m){
dis[len++]=m%10;
m=m/10;
}
ans1[0]+=dfs1(len-1,1,1);
printf("%lld
",ans1[0]);
for(i=1;i<=9;i++){
ans1[i]+=dfs(len-1,1,i);
printf("%lld
",ans1[i]);
}
return 0;
}