HDU 4249 A Famous Equation：數位 DP 解方程計數

題意

給定形如 A+B=C 的等式，其中 A、B、C 為字符串，包含數字與 ?（通配符）。每個 ? 可替換為 0-9，但最高位不能為 0（除非該數長度為 1）。求合法填法數量。

數位 DP 狀態設計

dp[pos][a][b][c][carry]：

• pos：當前處理到第幾位（從低位到高位）。
• a,b,c：A、B、C 在該位的具體數字（0-9，若原字符為定值則固定）。
• carry：來自低位的進位（0 或 1）。

轉移：枚舉當前位可能的數字組合，滿足 (a + b + carry) % 10 == c，新進位 (a+b+carry)/10，累加下一狀態方案數。

邊界：pos > len 時，若 carry == 0 返回 1 否則 0。

代碼實現要點

• 將三字符串反轉對齊，不足長度補 '0'（非通配符）。
• 遞歸 + 記憶化（vis 數組打標）。
• 處理最高位非 0 限制：pos == lenX && digit == 0 && lenX != 1 跳過。

核心代碼片段

ll dp[15][10][10][10][2];
int vis[15][10][10][10][2], kase;
char A[15], B[15], C[15];
int len, lenA, lenB, lenC;

ll dfs(int pos, int a, int b, int c, int carry) {
    ll &res = dp[pos][a][b][c][carry];
    if (pos > len) return carry == 0;
    if (vis[pos][a][b][c][carry] == kase) return res;
    vis[pos][a][b][c][carry] = kase;
    res = 0;
    // 枚舉當前位數字，根據原字符是否為 '?' 分情況
    // ... 詳細分支見原代碼 ...
    return res;
}

int main() {
    char s[100];
    while (~scanf("%s", s+1)) {
        // 解析 A+B=C 字符串，反轉存入 A,B,C
        ++kase;
        printf("Case %d: %lld\n", kase, dfs(1,0,0,0,0));
    }
    return 0;
}