HDU 3652 B：數位 DP 統計含「13」且能被 13 整除的數

問題描述

給定 n（字符串形式，長度 ≤ 10），求 1 到 n 中滿足：包含子串 "13" 且能被 13 整除的數字個數。多測試用例，以 EOF 結束。

數位 DP 狀態設計

dp[pos][last][tight][has13][mod]：

• pos：當前處理到第幾位（0-index，高位到低位）
• last：上一位數字（0-9，初始 0）
• tight：前綴是否已小於 n（0=相等，1=已小）
• has13：是否已出現 "13"（0/1）
• mod：當前前綴模 13 的餘數（0-12）

返回值：滿足條件的方案數。

狀態轉移

枚舉當前位 d = 0..up（up = tight ? 9 : s[pos]-'0'）：

• ntight = tight || (d < up)
• nhas13 = has13 || (last==1 && d==3)
• nmod = (mod*10 + d) % 13
• 遞歸 dfs(pos+1, d, ntight, nhas13, nmod)

終止條件：pos == len，返回 (has13 && mod==0) ? 1 : 0。

代碼實現

#include 
using namespace std;
const int MAXL = 15;
int dp[MAXL][10][2][2][13];
int vis[MAXL][10][2][2][13], timer;
string s;
int len;

int dfs(int pos, int last, int tight, int has13, int mod) {
    if (pos == len) return (has13 && mod == 0) ? 1 : 0;
    int& res = dp[pos][last][tight][has13][mod];
    if (vis[pos][last][tight][has13][mod] == timer) return res;
    vis[pos][last][tight][has13][mod] = timer;
    res = 0;
    int up = tight ? 9 : s[pos] - '0';
    for (int d = 0; d <= up; ++d) {
        int ntight = tight || (d < up);
        int nhas13 = has13 || (last == 1 && d == 3);
        int nmod = (mod * 10 + d) % 13;
        res += dfs(pos + 1, d, ntight, nhas13, nmod);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> s) {
        len = s.size();
        ++timer;
        cout << dfs(0, 0, 0, 0, 0) << '\n';
    }
    return 0;
}

複雜度

• 狀態數：15 × 10 × 2 × 2 × 13 ≈ 7800
• 每狀態轉移：≤ 10 次循環
• 單測試用例：~8萬 操作，極快。

關鍵細節

1. 前導零處理：本題從 1 開始，無前導零干擾。若包含 0，需額外狀態 started 標記是否已出現非零位。
2. 模運算累積：nmod = (mod*10 + d) % 13 正確維護前綴模 13 餘數。
3. 多測試用例：用 timer 避免 memset。

舉一反三

同框架可解決：

• 包含特定子串 + 能被 K 整除
• 數字中不含特定模式（如無 "49"）
• 數位和/乘積滿足條件

只需修改 nhas13 判斷邏輯和模數大小。