解题思路: 递归,分段计算。

比如1~2974这个序列,将它拆成1~2970和2971~2974两部分,后者就是个位从1到4,这4个数字先各出现一次,然后2,9,7这3个数字分别出现了5次(虽然是从2971开始,但2970也要算上);前者的数位统计利用递推来解决,先只统计2969个位的这10个数出现的全部次数(从0数起),每个数都出现了297次。然后只用重复上述步骤,计算296这个数即可,但这时就相当于10个数地计算了。即每次向下一层计算时,乘子m要乘以10。归纳起来其实就是找f(k)和f(10*k+m)之间的关系。

代码如下:

#include <bits/stdc++.h>
using namespace std;
int small[12], big[12];
void cal(int n, int m){ //m是乘子,每次进入下一层乘10
    int x = n / 10;
    int y = n % 10;
    int temp = x;
    for(int i = 1; i <= y; i++) small[i] += m;//先数一数从10*x+1到10*x+y这段序列中不超过个位数的数的个数
    for(int i = 0; i < 10; i++) small[i] += m * x;//计算10*x-10到10*x-1这段序列中个位数的总个数
    while(temp){
        small[temp % 10] += m * (y + 1); //再数一数从10*x+0到10*x+y这段序列中非个位数的数的个数,注意不要算成10*x+1到10*x+y了
        temp /= 10;
    }
    if(x) cal(x - 1, m * 10);
}

int main(){
    int x, y;
    while(~scanf("%d%d", &x, &y)){
        if(x == 0 && y == 0) break;
        if(x > y) swap(x, y);
        memset(small, 0, sizeof(small));
        cal(y, 1);
        for(int i = 0; i < 10; i++) big[i] = small[i];
        memset(small, 0, sizeof(small));
        cal(x - 1, 1);
        for(int i = 0; i < 10; i++){
            printf("%d%c", big[i] - small[i], i == 9 ? '\n' : ' ');
        }
    }
    return 0;
}