UVA 11375 Matches：大整數 DP 計算火柴排列數

問題描述

有 n 根火柴，可組成數字 0-9（分別消耗 6,2,5,5,4,5,6,3,7,6 根）。火柴不必用完，不能有前導零。求能組成多少個不同的非負整數。

DP 狀態定義

`dp[i]` = 用恰好 i 根火柴能組成的數字個數（允許前導零的序列）。
初始 `dp[0] = 1`（空序列）。
轉移：對每個狀態 i，嘗試添加數字 d (0-9) → `dp[i + cost[d]] += dp[i]`。
去除前導零：初始時 `i=0` 不能添加 0；最後補上單個數字 0（需 6 根火柴，`dp[6] += 1`）。

前綴和優化查詢

因火柴可不完全用完，答案為 `sum_{i=1..n} dp[i]`。預計算前綴和 `ans[i] = ans[i-1] + dp[i]`，查詢 O(1)。

大整數實現

結果極大（n=2000 時超千位），需高精度加法。用結構體存十進制數組，實現 `operator+`。

完整代碼

#include 
#include 
#include 
using namespace std;

const int MAXN = 2005;
struct BigInt {
    int d[510], len;
    BigInt(int v=0) { memset(d,0,sizeof(d)); len=0; if(v){ d[len++]=v; } }
    BigInt operator+(const BigInt& o) const {
        BigInt r; r.len = max(len, o.len);
        for(int i=0;i=0;--i) printf("%d",d[i]);
        puts("");
    }
} dp[MAXN], ans[MAXN];

int cost[10] = {6,2,5,5,4,5,6,3,7,6};

int main() {
    dp[0] = BigInt(1);
    for(int i=0;i<=2000;++i){
        for(int d=0;d<10;++d){
            if(i==0 && d==0) continue; // 無前導零
            if(i+cost[d] <= 2000) dp[i+cost[d]] = dp[i+cost[d]] + dp[i];
        }
    }
    dp[6] = dp[6] + BigInt(1); // 數字 0
    ans[0] = dp[0];
    for(int i=1;i<=2000;++i) ans[i] = ans[i-1] + dp[i];
    int n;
    while(scanf("%d",&n)==1 && n) ans[n].print();
    return 0;
}

總結

經典「火柴棒數字」DP，關鍵在於前導零處理（初始狀態禁止加 0，最後單獨加 0）與大整數加法。狀態轉移為完全背包形式，順序遍歷 i 即可。