POJ 2506 Tiling：高精度遞推與大整數加法

POJ 2506 Tiling：高精度遞推與大整數加法

題目：2×n 的條形區域，用 2×1 和 2×2 的磚塊鋪滿，求方案數。n ≤ 250，答案極大，需高精度處理。

遞推關係推導

考慮最右側的放置方式：

• 放一個 2×1 豎向磚塊 → 剩餘 2×(n-1)，方案數 f[n-1]
• 放兩個 2×1 橫向磚塊 → 剩餘 2×(n-2)，方案數 f[n-2]
• 放一個 2×2 磚塊 → 剩餘 2×(n-2)，方案數 f[n-2]

得遞推式：f[n] = f[n-1] + 2·f[n-2]，初始 f[0]=1, f[1]=1, f[2]=3。

高精度大整數實現

採用基數 BASE=1000 的數組模擬大整數，每個元素存 3 位十進制數。實現加法運算並處理進位。輸出時最高位不補零，其餘位用 setw(3) setfill('0') 補零。

完整代碼

#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#define MAX 260
#define BASE 1000
using namespace std;

struct BigInt {
    int num[MAX], len;
    BigInt(int _ = 0) { memset(num, 0, sizeof(num)); if (_) { num[1] = _; len = 1; } else len = 0; }
    BigInt operator+(const BigInt &a) const {
        BigInt re; re.len = max(len, a.len);
        int temp = 0;
        for (int i = 1; i <= re.len; ++i) {
            re.num[i] = num[i] + a.num[i] + temp;
            temp = re.num[i] / BASE;
            re.num[i] %= BASE;
        }
        if (temp) re.num[++re.len] = temp;
        return re;
    }
} f[MAX];

ostream &operator<<(ostream &os, const BigInt &a) {
    os << a.num[a.len];
    for (int i = a.len - 1; i; --i)
        os << fixed << setfill('0') << setw(3) << a.num[i];
    return os;
}

int main() {
    f[0] = BigInt(1); f[1] = BigInt(1); f[2] = BigInt(3);
    for (int i = 3; i <= 250; ++i) f[i] = f[i-1] + f[i-2] + f[i-2];
    int x;
    while (scanf("%d", &x) != EOF) cout << f[x] << endl;
    return 0;
}

本題是高精度入門佳例，展示了「遞推建模 + 大整數模板」的標準解題套路。