HDU 3652 B-number：數位 DP 求含「13」且能被 13 整除的數字個數

問題描述

所謂「B-number」（wqb-number），指十進制表示中包含子串「13」且能被 13 整除的非負整數。給定 n (1 ≤ n ≤ 1,000,000,000)，求 1 到 n 中有多少個 B-number。多組測試數據，以 EOF 結束。

核心思路：數位 DP + 記憶化搜索

由於 n 高達 10⁹，暴力枚舉不可行。數位 DP 是處理「數字範圍內滿足特定性質的數字計數」的標準利器。本題需同時追蹤兩個條件：

1. 模 13 餘數：構建數字時維護當前前綴對 13 的餘數。
2. 是否出現「13」：需記住前一位是否為 1，以及是否已經出現過「13」。

狀態定義

int dp[15][13][3];
// dp[pos][mod][have]
// pos: 當前處理的位數（從高位到低位，1-based）
// mod: 當前前綴對 13 的餘數 (0~12)
// have: 0=未出現13且末位非1；1=未出現13但末位為1；2=已出現13

遞歸轉移

函數 dfs(pos, mod, have, lim) 返回合法方案數。lim 表示是否受上界 n 的對應位限制。

• 若 pos == 0：返回 (mod == 0 && have == 2) ? 1 : 0。
• 若 !lim && dp[pos][mod][have] != -1：直接返回記憶化結果。
• 枚舉當前位 i (0~9)（受 lim 限制）：
  • 新餘數 mod_x = (mod * 10 + i) % 13。
  • 更新 have_x：
    • 若 have == 0 && i == 1 → have_x = 1（末位變為 1）。
    • 若 have == 1 && i != 1 → have_x = 0（末位不再是 1，且未組成 13）。
    • 若 have == 1 && i == 3 → have_x = 2（組成「13」）。
    • 若 have == 2 → have_x = 2（已出現過，保持）。
  • 遞歸下一位：dfs(pos-1, mod_x, have_x, lim && i == num)。
• 若 !lim，存入 dp 並返回。

關鍵代碼片段

int dfs(int pos, int mod, int have, int lim) {
    if (pos <= 0) return (mod == 0 && have == 2);
    if (!lim && dp[pos][mod][have] != -1) return dp[pos][mod][have];
    int ans = 0;
    int num = lim ? s[pos] : 9;
    for (int i = 0; i <= num; ++i) {
        int mod_x = (mod * 10 + i) % 13;
        int have_x = have;
        if (have == 0 && i == 1) have_x = 1;
        else if (have == 1 && i != 1) have_x = 0;
        else if (have == 1 && i == 3) have_x = 2;
        ans += dfs(pos - 1, mod_x, have_x, lim && i == num);
    }
    if (!lim) dp[pos][mod][have] = ans;
    return ans;
}

主流程

1. 讀入 n，將其各位數字存入陣列 s[1..len]（低位在前）。
2. 初始化 dp 為 -1。
3. 調用 dfs(len, 0, 0, 1) 獲取答案並輸出。

複雜度與優化

• 狀態數：15 * 13 * 3 = 585，極小。
• 每狀態轉移 10 次，總操作數約 5,850 次/查詢，瞬間完成。
• 多組測試案例共用 dp 表（僅在 !lim 時記憶化），極其高效。

總結

本題是數位 DP 入門佳例，展示了如何將「包含特定子串」與「模運算」條件融合進狀態。關鍵在於 have 狀態的精心設計（0/1/2 三態），巧妙捕捉「13」的出現過程。同類技巧廣泛適用於「包含/不包含特定模式」的計數問題。