HDU 1250 Hat's Fibonacci - 大數四階斐波那契

題目描述

定義四階斐波那契數列：

F(1)=F(2)=F(3)=F(4)=1
F(n) = F(n-1)+F(n-2)+F(n-3)+F(n-4)  (n>4)

輸入多組整數 n（至 EOF），每組輸出 F(n)。測資保證 F(n) 不超過 2005 位數。

解題關鍵：大整數處理

由於 n 可達數千，結果位數極大，必須使用大整數庫。Java 原生 BigInteger 完美適配；C++ 需自行實現高精度加法或使用 boost::multiprecision::cpp_int。

預計算策略

1. 讀取所有輸入，記錄最大 n_max。
2. 或直接預計算至足夠大（如 10000）覆蓋所有測資。
3. 陣列 f[i] 存儲第 i 項，迭代填表：f[i] = f[i-1]+f[i-2]+f[i-3]+f[i-4]。
4. 查詢時直接輸出 f[n]，單次查詢 O(1)。

Java 參考實作

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        final int MAX_N = 10000;
        BigInteger[] f = new BigInteger[MAX_N + 1];
        f[1] = f[2] = f[3] = f[4] = BigInteger.ONE;
        for (int i = 5; i <= MAX_N; ++i) {
            f[i] = f[i-1].add(f[i-2]).add(f[i-3]).add(f[i-4]);
        }
        while (in.hasNextInt()) {
            int n = in.nextInt();
            System.out.println(f[n]);
        }
    }
}

C++ 參考實作（Boost）

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int MAX_N = 10000;
    vector<cpp_int> f(MAX_N + 1);
    f[1] = f[2] = f[3] = f[4] = 1;
    for (int i = 5; i <= MAX_N; ++i)
        f[i] = f[i-1] + f[i-2] + f[i-3] + f[i-4];
    int n;
    while (cin >> n) cout << f[n] << '\n';
    return 0;
}

複雜度與限制

• 預計算：O(MAX_N * D)，D 為大數位數（≤2005），極快。
• 記憶體：約 10000 × 2005 bits ≈ 2.5 MB，遠小於限制。
• 輸入至 EOF，需使用 while(cin>>n) 或 scanf 循環。

常見坑點

• ❌ 遞迴計算導致指數級爆炸 → 必須迭代 DP。
• ❌ 使用 64 位整數溢位 → 必須大整數。
• ❌ 未預計算，每查詢重算 → TLE。