HDU 4722 Good Numbers：數位 DP 統計各位數字和能被 10 整除的數字個數

題目描述

若數字各位之和能被 10 整除，稱為 Good Number。給定區間 [A, B]（0 ≤ A ≤ B ≤ 10^18），求 Good Number 個數。T ≤ 10000。

數位 DP 狀態

dp[pos][mod]：從高位到低位處理到第 pos 位（0 為最低位），當前數字和模 10 為 mod 的方案數。pos 最大 19（10^18 19 位）。

遞歸 + 備忘錄

long long dp[20][10];
bool vis[20][10];
int digits[20];

long long dfs(int pos, int mod, bool limit) {
    if (pos == -1) return mod == 0;
    if (!limit && vis[pos][mod]) return dp[pos][mod];
    int up = limit ? digits[pos] : 9;
    long long ans = 0;
    for (int d = 0; d <= up; ++d)
        ans += dfs(pos-1, (mod + d) % 10, limit && d == up);
    if (!limit) { vis[pos][mod] = true; dp[pos][mod] = ans; }
    return ans;
}

long long solve(long long x) {
    if (x < 0) return 0;
    int len = 0;
    while (x) { digits[len++] = x % 10; x /= 10; }
    return dfs(len-1, 0, true);
}

查詢答案

ans = solve(B) - solve(A-1)。每次查詢 O(19*10*10) 極快，支援 T=10000。

複雜度

• 預計算：無，按需填表。
• 單次查詢：O(位數 * 10 * 10) ≈ 2000 操作。
• 空間：O(20*10)。

總結

數位 DP 核心模板：dfs(pos, state, limit)。狀態為「模 10 餘數」，轉移枚舉當前位數字。掌握此模板可解決「區間內滿足數字屬性計數」大類問題。