题解 | [ZJOI2010]COUNT 数字计数

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

// 统计[1..n]中每个数字0..9出现的次数；n<=1e12
vector<int64> tally(int64 n) {
    vector<int64> cnt(10, 0);
    if (n <= 0) return cnt;

    for (int64 p = 1; p <= n; p *= 10) {      // p: 个位/十位/百位...
        int64 high = n / (p * 10);
        int64 cur  = (n / p) % 10;
        int64 low  = n % p;

        // 1..9 的通用公式
        for (int d = 1; d <= 9; ++d) {
            if (cur > d)      cnt[d] += (high + 1) * p;
            else if (cur == d)cnt[d] += high * p + low + 1;
            else              cnt[d] += high * p;
        }
        // 0 的特殊处理：最高位不允许为0，等价于把high减1（若high>0）
        if (high > 0) {
            if (cur == 0) cnt[0] += (high - 1) * p + low + 1;
            else          cnt[0] += (high - 1) * p + p;
        }
    }
    return cnt;
}

int main() {
    

    long long a, b;
    if (!(cin >> a >> b)) return 0;
    if (a > b) swap(a, b);

    auto R = tally(b);
    auto L = tally(a - 1);
    for (int d = 0; d <= 9; ++d) {
        cout << (R[d] - L[d]) << (d == 9 ? '\n' : ' ');
    }
    return 0;
}