HDU 2089：不要 62——數位 DP 計數不含 4 和 62 的數字

題目描述

統計區間 [n, m] 内不含數字 4 和連續 62 的整數個數。0 < n ≤ m < 1,000,000。

數位 DP 狀態定義

dp[i][state]：前 i 位（從高到低），狀態為 state 的合法數字個數。

• state 0：無不吉利數字
• state 1：無不吉利數字，且最高位是 2（下一位若為 6 會形成 62）
• state 2：已包含不吉利數字

遞推公式（預計算 1~7 位）

dp[i][0] = dp[i-1][0]*9 - dp[i-1][1]  // 排除首位為 4 和 62
dp[i][1] = dp[i-1][0]                 // 僅首位為 2
dp[i][2] = dp[i-1][2]*10 + dp[i-1][1] + dp[i-1][0] // 已非法或新形成非法

查詢函數 solve(x)：計算 [0, x) 合法數個數

逐位處理，根據當前位數字累加對應 dp 值，標記是否已進入非法狀態。

C++ 實現（核心）

int dp[10][3], a[10];
void init() {
    dp[0][0] = 1;
    for (int i = 1; i <= 7; ++i) {
        dp[i][0] = dp[i-1][0]*9 - dp[i-1][1];
        dp[i][1] = dp[i-1][0];
        dp[i][2] = dp[i-1][2]*10 + dp[i-1][1] + dp[i-1][0];
    }
}
int solve(int num) {
    int k=0, ans=0, sum=num, flag=0;
    while (num) a[++k] = num%10, num/=10;
    a[k+1] = 0;
    for (int i = k; i >= 1; --i) {
        ans += dp[i-1][2] * a[i];
        if (flag) ans += dp[i-1][0] * a[i];
        if (!flag && a[i] > 4) ans += dp[i-1][0];
        if (!flag && a[i+1]==6 && a[i] > 2) ans += dp[i][1];
        if (!flag && a[i] > 6) ans += dp[i-1][1];
        if (a[i]==4 || (a[i+1]==6 && a[i]==2)) flag = 1;
    }
    return sum - ans; // 總數 - 非法數 = 合法數
}
int main() {
    init();
    int l, r;
    while (scanf("%d%d", &l, &r), l|r)
        printf("%d\n", solve(r+1) - solve(l));
    return 0;
}

複雜度

• 預計算：O(1)
• 單次查詢：O(log m) ≈ 7 步