POJ 3286 How many 0's? —— 數位 DP 計數區間內 0 的個數

POJ 3286 要求計算閉區間 [n, m] 內所有整數十進制表示中數字 0 出現的總次數。資料範圍較大，必須用 數位 DP 或 數學推導 在 O(log₁₀ max) 內求解。

一、核心思路：逐位計算貢獻

以 2034 為例，枚舉 0 在個、十、百、千位出現的次數：

• 個位：高位 203 可取 1~203，共 203 次。
• 十位：高位 20，低位 0~9，共 20 × 10 = 200 次。
• 百位：當前位上限為 0，高位 1 時低位 0~99（100 次），高位 2 時低位 0~34（35 次），共 135 次。
• 千位：最高位不能為 0，貢獻 0。

總計 203 + 200 + 135 = 538。

二、通用公式推導

設 p[i] = 10ⁱ。對第 i 位（從 1 開始）：

high = x / p[i];        // 高位部分
cur  = (x / p[i-1]) % 10; // 當前位
low  = x % p[i-1];        // 低位部分

if (cur > 0)  ans += high * p[i-1];
else          ans += (high - 1) * p[i-1] + low + 1;

循環直到 p[i] > x 結束。最後用 solve(m) - solve(n-1) 得到區間答案。

三、完整 AC 代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXP = 20;
LL p[MAXP];

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

// 計算 0~x 中 0 的總個數
LL solve(LL x) {
    if (x < 0) return 0; // 兼容 n=0 時 n-1=-1
    LL ans = 0;
    for (int i = 1; ; ++i) {
        LL high = x / p[i];
        LL cur  = (x / p[i-1]) % 10;
        LL low  = x % p[i-1];

        if (cur > 0) ans += high * p[i-1];
        else         ans += (high - 1) * p[i-1] + low + 1;

        if (p[i] > x) break;
    }
    return ans;
}

int main() {
    init();
    LL n, m;
    while (cin >> n >> m) {
        if (n == -1 && m == -1) break;
        if (n > m) swap(n, m);
        printf("%lld\n", solve(m) - solve(n-1));
    }
    return 0;
}

四、關鍵細節

1. solve(-1) 返回 0，保證 n=0 時 solve(n-1) 不出錯。
2. 輸入以 -1 -1 結束，需判斷跳出。
3. 用 long long 防止溢位，p[18] = 10¹⁸ 足夠覆蓋 64 位整數範圍。

五、複雜度

時間 O(log₁₀ max(m))，空間 O(1)，極其高效。