HDOJ 1663：The Counting Problem - 數位 DP 與打表法詳解

問題描述

給定區間 [a, b] (0 < a, b < 10^8)，統計寫出所有整數時，每個數字 0-9 出現的總次數。最多 500 組查詢。

核心思路：預計算 + 遞推

直接逐個數字統計會超時。觀察規律：對於 10^k 以內的數字，各位出現次數有固定模式。預先打表 cnt[len][digit] 表示 10^len 範圍內（即 0 ~ 10^len - 1）各數字出現次數。

遞推公式

• cnt[0][0] = 1，其餘 0。
• 對於長度 len：最高位固定為 d (1~9) 時，低位遞歸為 len-1 位全排列；最高位為 0 時不計入（避免前導零）。
• 實際代碼中通過掃描數字每一位，累加對應表值，並處理「前導零」與「中間零」的特殊情況。

代碼實現 (關鍵邏輯)

// 預計算 noZero[len][d]：不考慮前導零時，len 位數中數字 d 出現次數
// 以及 zeroFix[len]：補零修正值

long long solve(long long x) {
    if (x < 0) return 0;
    if (x == 0) return 1; // 僅數字 0
    vector<int> digits;
    while (x) { digits.push_back(x % 10); x /= 10; }
    reverse(digits.begin(), digits.end());
    int len = digits.size();
    long long ans[10] = {0};

    // 1. 處理最高位之前的完整塊
    for (int i = 0; i < len - 1; ++i) {
        for (int d = 1; d <= 9; ++d) // 最高位 1-9
            for (int k = 0; k < 10; ++k)
                ans[k] += noZero[i][k];
    }

    // 2. 處理最高位
    for (int d = 1; d < digits[0]; ++d) {
        for (int k = 0; k < 10; ++k)
            ans[k] += noZero[len-1][k];
    }
    ans[digits[0]] += 1; // 最高位本身

    // 3. 遞歸處理低位（略，實際代碼掃描每一位並累加）
    // ...

    // 4. 處理 0 的特殊修正（前導零不計，中間零需補）
    // 使用 zeroFix 表

    return ans;
}

完整代碼結構

完整代碼包含三大表：

• noZero[len][10]：無前導零時的計數表。
• zeroFix[len]：補零修正值（處理類似 5050 中間零的情況）。
• fullBlock[len][10]：完整塊 [0, 10^len-1] 的計數（含前導零）。

查詢時計算 solve(b) - solve(a-1)。

複雜度

• 預計算：O(10 * 10) = O(1)。
• 單次查詢：O(log b)，極快。

總結

本題是「數位 DP」的經典打表變體，關鍵在於將「前導零不計」與「中間零需計」分離處理，預計算各長度塊的貢獻，實現 O(log n) 查詢。