HDU 1sting：斐波那契數列與大數加法結合求 1/2 字符串組合數

HDU 1sting：斐波那契數列與大數加法結合求 1/2 字符串組合數

給定由字符 '1' 組成的字符串，可將任意兩個相鄰 '1' 合併為 '2'，或保留 '1'。求長度為 n 的全 1 字符串能生成多少種不同結果字符串。n ≤ 200，多測試用例。

規律發現：斐波那契數列

設 f[n] 為長度 n 的答案。
考慮第一個字符：

• 保留 '1' → 剩餘 n-1 位任意組合：f[n-1] 種；
• 與第二個合併為 '2' → 剩餘 n-2 位任意組合：f[n-2] 種。

遞推：f[n] = f[n-1] + f[n-2]，f[1]=1, f[2]=2。即斐波那契數列第 n+1 項。
n=200 時 f[200] 約 42 位十進制數，超出 64 位整數，必須用大整數加法。

大整數實現（十進制數組模擬）

int num[210][1000];   // num[i][j] 存 f[i] 第 j 位（低位在前）
int len[210];          // 每個數的有效位數

// 初始化
num[1][0] = 1; len[1] = 1;
num[2][0] = 2; len[2] = 1;

// 預計算 f[3] ~ f[200]
for (int i = 3; i <= 200; ++i) {
    int carry = 0;
    for (int j = 0; j < len[i-1]; ++j) {
        int sum = carry + num[i-1][j] + num[i-2][j];
        num[i][j] = sum % 10;
        carry = sum / 10;
    }
    // 處理高位進位
    if (carry || num[i][len[i-1]]) len[i] = len[i-1] + 1;
    else len[i] = len[i-1];
}

完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210, MAXL = 1000;
int num[MAXN][MAXL], len[MAXN];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    // 大數斐波那契預計算
    num[1][0] = 1; len[1] = 1;
    num[2][0] = 2; len[2] = 1;
    for (int i = 3; i < MAXN; ++i) {
        int carry = 0;
        for (int j = 0; j < len[i-1]; ++j) {
            int sum = carry + num[i-1][j] + num[i-2][j];
            num[i][j] = sum % 10;
            carry = sum / 10;
        }
        if (carry) num[i][len[i-1]] = carry;
        len[i] = (num[i][len[i-1]] != 0) ? len[i-1] + 1 : len[i-1];
    }

    int T; cin >> T;
    string s;
    while (T--) {
        cin >> s;
        int n = s.length();
        for (int i = len[n] - 1; i >= 0; --i) cout << num[n][i];
        cout << '\n';
    }
    return 0;
}

關鍵細節

• 大數數組 num[i][j] 低位在前（j=0 為個位），輸出時逆序打印；
• len[i] 維護有效長度，避免輸出前導零；
• 預計算一次 O(MAXN × MAXL)，查詢 O(1) 輸出；
• 輸入字符串可能很長，用 string 讀取再取 length()。

複雜度

• 預計算：O(200 × 100) ≈ 2×10^4 操作；
• 查詢：O(位數) 輸出；
• 空間：210 × 1000 × 4B ≈ 0.8 MB。

樣例驗證

輸入：
3
1
11
11111

輸出：
1
2
8
解釋：f[1]=1, f[2]=2, f[5]=8 (1,2,3,5,8...)

此題將「組合計數 → 斐波那契遞推 → 大數加法」三步串聯，是入門級「找規律 + 高精度」的經典訓練題。