比赛 2022级DP专题练习赛4 评测结果 AAAAAAAAAA
题目名称 数字统计 最终得分 100
用户昵称 zxhhh 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2023-02-20 21:32:21
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;

const int N = 15;
typedef long long ll;

ll dp[N][N][N], a, b;

void init () {
	for (int i = 0;i <= 9;i++) for (int j = 0;j <= 9;j++) dp[1][i][j] = (i == j);//, cout << "1 " << i << " " << j << " " <<dp[1][i][j] <<endl; 
	for (int l = 2;l <= 12;l++) {
		for (int i = 0;i <= 9;i++) {
			for (int j = 0;j <= 9;j++) {
				for (int z = 0;z <= 9;z++) {
					dp[l][i][j] += dp[l - 1][z][j];
//					else dp[l][i][j] += dp[l - 1][z][j];
				}
				if (i == j) dp[l][i][j] += pow(10, l - 1);
//				cout << l << " " << i << " " << j << " " << dp[l][i][j] << endl;
			}
//			cout << l << " " << i << " " <<dp[l][i][0] << endl;
		}
	}
}

int c[N];
ll res1[N], res2[N], k[N];

void ans (ll x, ll res[]) {
	if (!x) {
		res[0] = 1;
		return;
	}
	int idx = 0; 
//	memset(res, 0, sizeof(res));
	while (x) c[++idx] = x % 10, x /= 10;
	for (int i = 1;i <= idx;i++) k[i] = k[i - 1] + pow(10, i - 1) * (ll)c[i];
	for (int i = idx;i >= 1;i--) {
		for (int j = 0;j < c[i];j++) for (int z = 0;z <= 9;z++) {
			if (!(i == idx && j == 0 && z == 0)) res[z] += dp[i][j][z];
			else {
				for (int l = i - 1;l >= 1;l--)for (int q = 1;q <= 9;q++) res[0] += dp[l][q][0];
			}
		}
		res[c[i]] += k[i - 1] + 1;
//		cout << i <<" " << res[0] << endl;
//		for (int j = 0;j <= 9;j++) cout << i << ' ' << j << " " << res[j] << endl;
	}
	res[0]++;
}

int main () {
	freopen("countzj.in", "r", stdin);
	freopen("countzj.out", "w", stdout);
	cin >> a >> b;
	init ();
	ans(a - 1, res1); ans(b, res2);
	for (int i = 0;i <= 9;i++) cout << res2[i] - res1[i] << " ";
	return 0;
}