给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

1 99

9 20 20 20 20 20 20 20 20 20

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long

LL read() {
	LL x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
	return x * f;
}

#define maxn 20
LL f[maxn][maxn][maxn], ans[maxn], ten[maxn];

void sum(LL x, int fl) {
	if(x < 0) return ;
	if(!x) ans[0] += fl;
	LL tot[maxn], tx = x;
	memset(tot, 0, sizeof(tot));
	int num[maxn], cnt = 0;
	while(x) num[++cnt] = x % 10, x /= 10;
	for(int k = 0; k <= 9; k++)
		for(int i = 1; i < cnt; i++)
			for(int j = (i == 1 ? 0 : 1); j <= 9; j++) tot[k] += f[k][i][j];
//	for(int i = 0; i <= 9; i++) printf("%lld%c", tot[i], i < 9 ? ‘ ‘ : ‘\n‘);
	for(int i = cnt; i; i--) {
		LL sum = 0;
		for(int k = 0; k <= 9; k++)
			for(int j = (i == cnt && i > 1 ? 1 : 0); j < num[i]; j++) tot[k] += f[k][i][j];
		tot[num[i]] += tx % ten[i-1] + 1;
	}
//	for(int i = 0; i <= 9; i++) printf("%lld%c", tot[i], i < 9 ? ‘ ‘ : ‘\n‘);
	for(int i = 0; i <= 9; i++) ans[i] += tot[i] * fl;
	return ;
}

int main() {
	ten[0] = 1;
	for(int i = 1; i < 13; i++) ten[i] = ten[i-1] * 10;
	for(int k = 0; k <= 9; k++) f[k][1][k] = 1;
	for(int k = 0; k <= 9; k++)
		for(int i = 1; i <= 13; i++)
			for(int j = 0; j <= 9; j++) {
//				if(k == 1) printf("%d %d %d: %lld\n", k, i, j, f[k][i][j]);
				for(int x = 0; x <= 9; x++)
					f[k][i+1][x] += f[k][i][j] + (x == k) * ten[i-1];
			}
	
	LL a = read(), b = read();
	sum(b, 1); sum(a - 1, -1);
	for(int i = 0; i <= 9; i++) printf("%lld%c", ans[i], i < 9 ? ‘ ‘ : ‘\n‘);
	
	return 0;
}