//数位统计dp
/*
数位dp的核心是进行分类讨论,思路是写一个函数count(n,x)求数字n从1到n中0~9出现的次数,求数字n每一位中x(0~9)出现的次数,把n所有位的
x出现次数累加,就是数字n从1~n 中x出现的次数。若要求从a到b(a <= b)闭区间内x出现的次数,可以用前缀和,count(b,x)-count(a-1,x)
分类讨论:
vector<int> num; num[i]是n第i位的数值
例如,数字为abcdefg,求第四位d所在位置x(0~9)出现的次数,此时num[i]中的i == 3
1. xxxdyyy d前高位取值:000 ~ abc-1 d后低位取值: 000 ~ 999 共abc * 1000 (即abc * 10^i)种选法
2. abcdyyy d前取值abc,讨论d后低位的取值情况
1) d < x , 那么abcxyyy > abcdefg,取不到abcxyyy,共0种选法
2) d == x, 那么abcd后只能取0~efg,共efg+1种取法
3) d > x , 那么abcdyyy > abcxefg 严格成立,yyy取0~999,共1000(10^i)种选法
特殊边界值的处理:
1. x取0时,注意两点,一是0不能在最高位num.size()-1位,这样0xxxx中最高位为0失去了计算的意义,最高位不能为前导0,从num.size()-2位
开始;二是在一般情况下计数中,当取xxx0yyy时,0前面的num.size()-2 ~ i+1位取法不是000~abc-1,而是001~abc-1,若有前导0计数失去意义
2. x非0时,一是取最高位num.size()-1位时,前面没有数,取000 ~ -1不合法,只能计算第2类的次数;
二是在取最低位0位时,0位后面一直都是取000~000,即1种取法,所以计算10^i时,当i为0时,10^i为1
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
//计算数字n从高位l到低位r的数字
int get(vector<int> num,int l,int r){
int res = 0;
//每一次添加i位之前将res向高位左移一位,然后加上i位数值到个位
for(int i = l;i >= r;i--) res = res*10 + num[i];
return res;//l < r时返回0
}
//计算10的i次方
int power10(int x){
int res = 1;//当i为0时,保证了10^0为1
while(x--) res *= 10;
return res;
}
//计算从1到n中所有位x出现的次数
int count(int n,int x){
if(!n) return 0;//若a-1为0,那么返回0,否则向下执行num[i]没有插入数字
//将n每一位的数字依次存入数组
vector<int> num;
while(n){
num.push_back(n%10);//插入此时n的个位数
n /= 10;//n的位进行右移,高位向低位移一位
}
//遍历数字n的所有位次,并将x在每位出现的次数进行累加
n = num.size()-1;
int res = 0;
for(int i = 0;i <= n-!x;i++){ //x为0时最高位从num.size()-2开始
//x位于最高位时,不计算第1类
if(i < n){ //第1类选法
res += (get(num,n,i+1)-!x) * power10(i);//x为0时,选法共(abc-1) * 10^i种
}
//计算第二类,第1小类选法为0,不用考虑,判断2和3小类即可
if(num[i] == x) res += get(num,i-1,0)+1;
else if(num[i] > x) res += power10(i);
}
return res;
}
int main(){
int a,b;
while(cin >> a >> b,a){ //a为0时停止输入,输入应保证a,b > 0
if(a > b) swap(a,b);
for(int i = 0;i < 10;i++){
cout << count(b,i)-count(a-1,i) << ' ';
}
cout << endl;
}
return 0;
}