UVa 1640：區間數字頻率統計（數位DP思路）

題目大意

給兩個整數 a, b (a ≤ b)，統計區間 [a, b] 中每個十進制數字 0~9 出現的總次數。例如 1024 到 1032，共 10 個數，0 出現 10 次，1 出現 10 次，等。

核心思路：前綴計數函數 f(n) = [0, n] 中各數字頻率

答案 = f(b) - f(a-1)。關鍵是高效計算 f(n)。

遞歸分解法（按位遞歸）

將 n 按最高位分解。例如 n = 3426：
[0, 3426] = [0, 2999] + [3000, 3399] + [3400, 3419] + [3420, 3426]。
每段內低位均勻分布，高位固定，可直接用組合公式計算。

關鍵遞歸公式

• 設 calc(s, cnt) 計算字符串 s 表示的數 n 的 [0, n] 頻率，累加到 cnt[10]。
• 最高位 d = s[0]-'0'，長度 len。
  1. 高位 0~d-1：每個高位出現 10^len-1 次，低位全排列，每個數字出現 (len-1) * 10len-2 次。
  2. 高位 d：出現 (n % 10^len-1 + 1) 次。
  3. 遞歸處理低位部分。
• 最後減去前導 0 的計數：對每個位數長度 L，最高位不能為 0，故減去 10L-1 次 0。

代碼框架 (C++)

#include 
#include 
using namespace std;

void calc(char* s, long long cnt[]) {
    int len = strlen(s);
    if (len == 1) {
        for (int i = 0; i <= s[0]-'0'; ++i) cnt[i]++;
        return;
    }
    int d = s[0] - '0';
    int p10 = 1;
    for (int i = 1; i < len; ++i) p10 *= 10;
    // 高位 0~d-1
    for (int i = 1; i < d; ++i) cnt[i] += p10;
    // 低位全排列部分
    for (int i = 0; i < 10; ++i) cnt[i] += (long long)d * (len-1) * (p10/10);
    // 高位 d
    cnt[d] += atoi(s+1) + 1;
    // 遞歸低位
    calc(s+1, cnt);
}

int main() {
    long long a, b;
    while (scanf("%lld%lld", &a, &b) == 2) {
        if (a > b) swap(a, b);
        long long ca[10]={0}, cb[10]={0};
        char sa[20], sb[20];
        sprintf(sa, "%lld", a-1);
        sprintf(sb, "%lld", b);
        if (a > 0) calc(sa, ca);
        calc(sb, cb);
        // 減去前導 0（略，完整代碼需按位長減去）
        for (int i = 0; i < 9; ++i) printf("%lld ", cb[i]-ca[i]);
        printf("%lld\n", cb[9]-ca[9]);
    }
    return 0;
}

完整處理前導 0 的技巧

最簡潔做法：在 calc 內對每個位數長度 L，將 0 的計數減去 10L-1。或單獨寫一個 countZero(n) 函數計算前導 0 總數。

複雜度

• 時間：O(log₁₀ n) 每次查詢，極快。
• 空間：O(1)。

總結

UVa 1640 是經典的「區間數字頻率」問題。核心是 f(n) 的遞歸分解：按最高位拆分，利用低位全排列的均勻性直接計算，最後修正前導 0。掌握此模板，可解決所有類似「1 到 n 中數字 x 出現次數」的問題。