HDU 3555 Bomb：數位 DP 統計包含「49」的數字個數

問題描述

統計 1 到 N（N ≤ 2⁶³-1）中包含子序列「49」的數字個數。多測試用例 T ≤ 10000。

數位 DP 模板

狀態：dfs(pos, pre, has49, limit)

• pos：當前處理位置（從高位到低位）
• pre：前一位數字
• has49：是否已出現「49」
• limit：是否受 N 的對應位限制

狀態轉移

ll dfs(int pos, int pre, bool has49, bool limit) {
    if (pos == -1) return has49;  // 到達最低位，若已含49計1
    if (!limit && dp[pos][pre][has49] != -1) return dp[pos][pre][has49];
    
    int up = limit ? digit[pos] : 9;
    ll res = 0;
    for (int d = 0; d <= up; ++d) {
        bool nHas49 = has49 || (pre == 4 && d == 9);
        res += dfs(pos-1, d, nHas49, limit && d==up);
    }
    if (!limit) dp[pos][pre][has49] = res;
    return res;
}

完整代碼

#include 
using namespace std;
using ll = long long;

ll dp[20][10][2];
int digit[20];

ll dfs(int pos, int pre, bool has49, bool limit) {
    if (pos < 0) return has49;
    if (!limit && dp[pos][pre][has49] != -1) return dp[pos][pre][has49];
    int up = limit ? digit[pos] : 9;
    ll res = 0;
    for (int d = 0; d <= up; ++d) {
        res += dfs(pos-1, d, has49 || (pre==4 && d==9), limit && d==up);
    }
    if (!limit) dp[pos][pre][has49] = res;
    return res;
}

ll solve(ll x) {
    int len = 0;
    while (x) { digit[len++] = x % 10; x /= 10; }
    return dfs(len-1, 0, false, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dp, -1, sizeof(dp));
    int T; cin >> T;
    while (T--) {
        ll n; cin >> n;
        cout << solve(n) << '\n';
    }
    return 0;
}

關鍵點總結

擴展：統計不包含「49」的數

總數 N 減去包含「49」的數，或修改 DP 返回 !has49。同類問題：「不要 62」（HDU 2089）、「666」（HDU 3652）等。

複雜度

• 預處理：O(1)
• 單次查詢：O(位數 × 狀態數) = O(19 × 10 × 2) ≈ 380 操作
• 10000 測試用例總計 < 4×10⁶ 操作，極快