ACM 題目解析：數的計數問題

問題描述

給定範圍 [L, R]，統計滿足特定數字屬性（如包含某數字、數位和為特定值、無重複數字等）的整數個數。這類「數位 DP」問題是 ACM 競賽高頻考點，NJUPT OJ 1050 即為典型代表。

數位 DP 核心框架

狀態定義

dfs(pos, tight, lead, state...)

• pos：當前處理到第幾位（從高位到低位）
• tight：前綴是否已達到上界限制
• lead：是否仍處於前導零階段
• state：業務相關狀態（如：數位和、餘數、掩碼、上一位數字等）

遞歸轉移

long long dfs(int pos, bool tight, bool lead, ...) {
    if (pos == -1) return check(state); // 到達最低位，判斷是否合法
    if (!tight && !lead && memo[pos][state] != -1) return memo[pos][state];
    int up = tight ? digits[pos] : 9;
    long long ans = 0;
    for (int d = 0; d <= up; ++d) {
        ans += dfs(pos-1, tight && d==up, lead && d==0, new_state);
    }
    if (!tight && !lead) memo[pos][state] = ans;
    return ans;
}

常見狀態設計

優化技巧

• 記憶化搜索：僅在 !tight && !lead 時使用 memo，避免狀態污染。
• 預處理上界數組：將 R 分解為 digits[] 便於按位遍歷。
• 雙倍上界技巧：計算 [L, R] 答案 = solve(R) - solve(L-1)。
• 狀態壓縮：多條件組合時用位掩碼或元組編碼降低維度。

實戰模板

class DigitDP {
    vector digits;
    long long memo[20][STATE_MAX];
    long long dfs(int pos, bool tight, bool lead, int state) { ... }
public:
    long long solve(long long x) {
        digits.clear();
        while (x) digits.push_back(x%10), x/=10;
        memset(memo, -1, sizeof memo);
        return dfs(digits.size()-1, true, true, INIT_STATE);
    }
};

總結

數位 DP 將「數字性質」轉化為「數位序列約束」，通過位級遞歸+記憶化實現指數級剪枝。掌握狀態抽象、邊界處理、優化技巧三大核心，即可攻克絕大多數計數類問題。