BZOJ 1833 [ZJOI 2010] Count 數字計數 — 數位 DP 分情況處理前導零

題目

給定 n, m (≤ 10¹⁸)，統計區間 [n, m] 內所有整數中，數字 0~9 各出現多少次。

核心難點：前導零

數位 DP 通常按位遞歸。0 不能作為最高位，導致 0 的計數公式與 1~9 不同：

• 對數字 d ∈ [1,9]：高位可為 0，公式統一。
• 對 0：高位不可為 0，需扣除最高位為 0 的情況。

逐位貢獻法（非遞歸 DP，O(log n)）

對每一位 i (10^{i-1})，設 high = x / 10^i, cur = (x / 10^{i-1}) % 10, low = x % 10^{i-1}。
數字 k (1~9) 在該位出現次數：

if cur > k:  (high + 1) * 10^{i-1}
if cur == k:  high * 10^{i-1} + low + 1
if cur < k:   high * 10^{i-1}

數字 0：

if cur > 0:  high * 10^{i-1}
if cur == 0: (high - 1) * 10^{i-1} + low + 1  // high=0 時特判

C++ 實作

#include 
using namespace std;
using int64 = long long;
int64 p10[20], ans[10];

void init() { p10[0] = 1; for (int i=1;i<18;++i) p10[i]=p10[i-1]*10; }

void solve(int64 x, int f) {  // f=+1 加，f=-1 減
    if (x == -1) { ans[0]++; return; }
    for (int k=1;k<=9;++k)
        for (int i=1;;++i) {
            int64 high = x / p10[i];
            int64 cur  = (x / p10[i-1]) % 10;
            int64 low  = x % p10[i-1];
            if (cur > k) ans[k] += (high + 1) * p10[i-1] * f;
            else if (cur == k) ans[k] += (high * p10[i-1] + low + 1) * f;
            else ans[k] += high * p10[i-1] * f;
            if (p10[i] > x) break;
        }
    for (int i=1;;++i) {
        int64 high = x / p10[i];
        int64 cur  = (x / p10[i-1]) % 10;
        int64 low  = x % p10[i-1];
        if (cur > 0) ans[0] += high * p10[i-1] * f;
        else ans[0] += ((high - 1) * p10[i-1] + low + 1) * f;
        if (p10[i] > x) break;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int64 n, m; cin >> n >> m;
    solve(m, 1);
    solve(n-1, -1);
    for (int i=0;i<9;++i) cout << ans[i] << ' ';
    cout << ans[9] << '\n';
    return 0;
}

複雜度與注意

• 時間：O(log₁₀ m * 10)，極快。
• 注意 n=0 邊界：solve(-1) 特判只計數一個 0。
• 結果可能超 64 位？題目通常保證 64 位足夠，否則用 __int128 或大整數。