HDU 4249 A Famous Equation - 數位 DP 詳解

題目大意

給定形如 "A+B=C" 的等式，其中 A、B、C 為包含數字與 '?' 的字符串。'?' 可替換為任意數字 0-9，但最高位不能為 0（除非數字本身長度為 1）。求滿足等式的填法總數。

數位 DP 狀態設計

從低位向高位逐位處理，狀態定義為：

dp[pos][a][b][c][carry]
// pos: 當前處理到第 pos 位（從低位起，1-indexed）
// a, b, c: A、B、C 在該位的具體數字（若原字符為 '?' 則為枚舉值，否則為固定值）
// carry: 來自低位的進位（0 或 1）
// 返回值: 滿足條件的填法數

轉移邏輯

1. 根據原字符串確定該位可取數字集合。
2. 枚舉 A、B 該位數字（若為 '?' 則 0-9，注意最高位非 0 限制）。
3. 計算 sum = a + b + carry，當前位結果為 sum % 10，新進位為 sum / 10。
4. 檢查 C 該位是否匹配（若為 '?' 則允許任意匹配數字，同樣注意最高位限制）。
5. 遞歸至下一位，累加方案數。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 15;

int T, len, len1, len2, len3, kase = 0;
char a[MAXN], b[MAXN], c[MAXN], s[100];
int vis[MAXN][10][10][10][2];
ll dp[MAXN][10][10][10][2];

ll solve(int pos, int da, int db, int dc, int carry) {
    ll &res = dp[pos][da][db][dc][carry];
    if (pos > len) return carry == 0;
    if (vis[pos][da][db][dc][carry] == kase) return res;
    vis[pos][da][db][dc][carry] = kase;
    res = 0;

    // 獲取當前位允許的數字範圍
    auto getDigits = [&](char ch, int pos, int maxLen) -> vector<int> {
        vector<int> dig;
        if (ch == '?') {
            for (int d = 0; d <= 9; d++) {
                if (pos == maxLen && d == 0 && maxLen != 1) continue;
                dig.push_back(d);
            }
        } else {
            dig.push_back(ch - '0');
        }
        return dig;
    };

    vector<int> daList = getDigits(a[pos], pos, len1);
    vector<int> dbList = getDigits(b[pos], pos, len2);
    vector<int> dcList = getDigits(c[pos], pos, len3);

    for (int x : daList) {
        for (int y : dbList) {
            int sum = x + y + carry;
            int digit = sum % 10;
            int ncarry = sum / 10;
            for (int z : dcList) {
                if (z == digit) {
                    res += solve(pos + 1, x, y, z, ncarry);
                }
            }
        }
    }
    return res;
}

int main() {
    while (~scanf("%s", s + 1)) {
        len = strlen(s + 1);
        len1 = len2 = len3 = 0;
        int id = 0;
        for (int i = len; i >= 1; i--) {
            if (s[i] == '=' || s[i] == '+') { id++; continue; }
            if (id == 0) c[++len3] = s[i];
            else if (id == 1) b[++len2] = s[i];
            else a[++len1] = s[i];
        }
        len = max(len1, max(len2, len3));
        for (int i = len1 + 1; i <= len; i++) a[i] = '0';
        for (int i = len2 + 1; i <= len; i++) b[i] = '0';
        for (int i = len3 + 1; i <= len; i++) c[i] = '0';
        ++kase;
        ll ans = solve(1, 0, 0, 0, 0);
        printf("Case %d: %lld\n", kase, ans);
    }
    return 0;
}

關鍵點總結

• 字符串逆序存儲，低位在前，便於逐位處理。
• 高位補 '0' 統一長度，但需注意最高位非 0 約束僅針對原始最高位。
• 記憶化搜索避免重複計算，狀態數約 15×10×10×10×2 = 30,000，極快。
• 使用 kase 技巧替代 memset 清空 vis 數組，提高多測試用例效率。