[ZJOI2010] 숫자 개수

한눈에 디지털 dp오랫동안 조정하였다.

/**

 * Problem:Count

 * Author:Shun Yao

 * Time:2013.5.31

 * Result:Accepted

 * Memo:DP

 */



#include <cstdio>

#include <cstring>



long long ans[10], s[15], tmp[10], f[15][10][10];



void calc(long long b, char y) {

	long i, j, l, t, k;

	long long q;

	if (b == 0) {

		if (y)

			++ans[0];

		else

			--ans[0];

		return;

	}

	memset(s, 0, sizeof s);

	memset(f, 0, sizeof f);

	memset(tmp, 0, sizeof tmp);

	k = 0;

	while (b) {

		s[++k] = b % 10;

		b /= 10;

	}

	q = 1;

	for (i = 1; i <= k; ++i) {

		for (j = 0; j <= 9; ++j) {

			f[i][j][j] = q;

			for (l = 0; l <= 9; ++l)

				for (t = 0; t <= 9; ++t)

					f[i][j][l] += f[i - 1][t][l];

		}

		q *= 10;

	}

	if (k > 0) {

		for (j = 2; j <= k; ++j)

			tmp[s[j]] += s[1] + 1;

		for (l = 0; l <= 9; ++l)

			for (j = 0; j <= s[1]; ++j)

				tmp[l] += f[1][j][l];

	}

	q = 10;

	for (i = 2; i < k; ++i) {

		for (j = i + 1; j <= k; ++j)

			tmp[s[j]] += s[i] * q;

		for (l = 0; l <= 9; ++l)

			for (j = 0; j < s[i]; ++j)

				tmp[l] += f[i][j][l];

		q *= 10;

	}

	if (k > 2) {

		for (i = 0; i <= 9; ++i)

			tmp[i] += f[1][i][i];

		for (i = 2; i < k; ++i)

			for (j = 0; j <= 9; ++j)

				for (l = 1; l <= 9; ++l)

					tmp[j] += f[i][l][j];

		for (i = 1; i < s[k]; ++i)

			for (j = 0; j <= 9; ++j)

				tmp[j] += f[k][i][j];

	}

	for (i = 0; i <= 9; ++i)

		if (y)

			ans[i] = tmp[i];

		else

			ans[i] -= tmp[i];

}



int main() {

	long i;

	long long a, b;

	freopen("count.in", "r", stdin);

	freopen("count.out", "w", stdout);

	scanf("%lld%lld", &a, &b);

	calc(b, 1);

	calc(a - 1, 0);

	printf("%lld", ans[0]);

	for (i = 1; i <= 9; ++i)

		printf(" %lld", ans[i]);

	fclose(stdin);

	fclose(stdout);

	return 0;

}