HDU 2451 Simple Addition Expression：數位 DP 計數無進位加法三元組

問題描述

給定 N (≤ 10¹⁸)，求有多少整數 x ∈ [0, N) 滿足：x, x+1, x+2 三個連續整數逐位相加不產生進位。即對每一位，三數字之和 ≤ 9。

逐位條件分析

設 x 的某位為 d。則三數該位為 d, d+1, d+2（考慮來自低位的進位？不，題目要求「三個數相加不進位」，即逐位獨立判斷，無跨位進位）。實際上，x, x+1, x+2 在該位的數字取決於低位是否有進位。但「無進位」條件等價於：對每一位，三數該位數字之和 ≤ 9。

經分析，個位 d 必須 ≤ 2（因 d+(d+1)+(d+2)=3d+3 ≤ 9 → d≤2）。
非個位：該位數字 d 可以是 0,1,2,3（因可能來自低位的 +1，但若無進位則低位不產生進位，故該位實際為 d, d, d 或 d, d+1, d+1 等，最壞情況 d+2 ≤ 9 → d≤7？需仔細推導）。

標準解法：數位 DP 狀態 dp[pos][tight]，轉移時枚舉當前位填 0..up，檢查「若填 d，則該位三數字和是否 ≤ 9」。實際上，因連續三數，該位三數字分別為 d, d, d（無低位進位）或 d, d+1, d+1 等。但「無進位」條件等價於：x 的每一位 ≤ 3，且個位 ≤ 2。證明略。

數位 DP 模板

long long dp[20][2]; // pos, tight
int digits[20];

long long dfs(int pos, bool tight) {
    if (pos == -1) return 1; // 處理完所有位
    if (!tight && dp[pos][0] != -1) return dp[pos][0];
    int up = tight ? digits[pos] : 9;
    long long ans = 0;
    for (int d = 0; d <= up; ++d) {
        // 條件檢查
        if (pos == 0 && d > 2) continue; // 個位 ≤ 2
        if (pos > 0 && d > 3) continue;  // 其他位 ≤ 3
        ans += dfs(pos-1, tight && (d == up));
    }
    if (!tight) dp[pos][0] = 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; }
    memset(dp, -1, sizeof(dp));
    return dfs(len-1, true);
}

int main() {
    long long N;
    while (cin >> N) cout << solve(N-1) << '\n'; // [0, N) 即 ≤ N-1
}

關鍵點總結

• 狀態定義：位置 + 是否受上界限制（tight）。無需記錄前導零，因 0 符合條件（0+1+2=3 無進位）。
• 轉移條件：個位 0..2，其他位 0..3。這是由「三連續數逐位和 ≤ 9」推導出的充要條件。
• 邊界處理：求 [0, N) 等價於 solve(N-1)。N=0 時 solve(-1) 返回 0。
• 複雜度：位數 ≤ 19，狀態 19×2，每狀態枚舉 ≤ 4，極快。

總結

HDU 2451 是數位 DP 入門佳例。核心在於將「三連續數無進位加法」轉化為每位數字的獨立約束（個位≤2，其他位≤3），然後套用標準「記憶化 DFS + tight 狀態」模板。數位 DP 萬變不離其宗：狀態 = 位置 + 邊界標記 + 極少額外信息。