询问区间([a,b])中(1sim 9)出现的次数，0 < a, b < 100000000。
解
显然为数位递推，考虑试填法，现在关键是求出方案数，于是设(A[i])表示i位以内数字中0出现的次数，不含前导0,(B[i])为i位数字中(0sim 9)出现的次数，可以含前导0，不难有(其中(base[i]=10^i))，显然有
[B[i]=10 imes B[i-1]+base[i-1]
]
[A[i]=A[i-1]+9B[i-1]
]
边界：(A[0]=B[0]=0)
解释：对于(B[i]),显然与第i位填什么有关，只能填0~9(含前导0)，i-1位能够统计的数字个数翻10倍，然后对于第i位填上该个数字，剩下的数字自由组合有(base[i-1])，对于(A[i])，i-1位以内方案(A[i-1])，i位的方案是(9B[i-1])(只能填(1sim 9))。
于是对于一个数位题目，当我们处理好含前导0i位数字方案（前面的数字已经填好统计方案）和不含前导0i位以内的方案（前面的数字没有填好，不允许含前导0）的方程时，该题基本完成一半，罗嗦几句，帮助理解，对于(1sim 9)的数字而言只需要(B[i])数组即可，因为含前导0有两重意思都是等价的，一是i位数字上的含前导0的数的数字出现次数，二是i位以内的不含前导0的数的出现的次数，而0没有这个特殊待遇，于是得在维护一个(A[i])，剩下的照数位递推套路进行即可。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define ll long long
#define swap(x,y) x^=y^=x^=y
using namespace std;
int num[9];
ll A[9],B[9],base[9],at[10],bt[10];
il void prepare();
il void ask(int n,ll[]);
int main(){
int a,b;prepare();
while(scanf("%d%d",&a,&b),a&&b){
if(a>b)swap(a,b);
ask(a-1,at),ask(b,bt);
for(int i(0);i<10;++i)
printf("%lld ",bt[i]-at[i]);
putchar('
');
}
return 0;
}
il void ask(int n,ll ans[]){++n,num[0]&=0;
do num[++num[0]]=n%10,n/=10;while(n);
ans[0]=0;
for(int j(num[0]),k,l(0);j;--j){
for(k=0;k<num[j];++k)
ans[0]+=A[j-1]+base[j-1]*(l+!k);
if(!num[j])++l;
}ans[0]+=B[num[0]-1],ans[0]-=A[num[0]-1]+base[num[0]-1];
if(num[0]==1)++ans[0];
for(int i(1),j,k,l;i<10;++i)
for(j=num[0],l=ans[i]=0;j;--j){
for(k=0;k<num[j];++k){
ans[i]+=A[j-1]+base[j-1]*(l+(k==i));
}if(num[j]==i)++l;
}
}
il void prepare(){base[0]=1;
for(int i(1);i<9;++i)
base[i]=base[i-1]*10,A[i]=A[i-1]*10+base[i-1];B[1]=1;
for(int i(2);i<9;++i)B[i]=9*A[i-1]+B[i-1];
}