比赛 |
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;
}