HDU 1250 Hat's Fibonacci：四階線性遞推大整數計算

題目大意

定義四階 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)。結果不超過 2005 位十進制數字。

大整數處理策略

• C/C++：需手動實現大整數加法（數組模擬）或使用 GMP 庫
• Java：直接用 BigInteger，代碼極簡
• Python：原生支持任意精度整數

Java 完整代碼 (推薦)

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

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

C++ 手動大整數實現

#include 
#include 
#include 
using namespace std;

const int MAXN = 10000;
const int MAXD = 2010;  // 2005 位 + 余量
int f[MAXN][MAXD];
int len[MAXN];

void add(int a[], int b[], int c[]) {  // c = a + b
    int carry = 0, i = 0;
    for (; i < MAXD; i++) {
        int sum = a[i] + b[i] + carry;
        c[i] = sum % 10;
        carry = sum / 10;
        if (!carry && i >= len[0] && i >= len[1]) break;
    }
    // 更新長度...
}

int main() {
    // 初始化 f[1]..f[4] = 1
    // 預計算 f[5]..f[10000]
    // 查詢輸出：從高位到低位打印非零數字
    return 0;
}

遞推關係矩陣形式 (擴展)

[ F(n)   ]   [1 1 1 1] [F(n-1)]
[ F(n-1) ] = [1 0 0 0] [F(n-2)]
[ F(n-2) ]   [0 1 0 0] [F(n-3)]
[ F(n-3) ]   [0 0 1 0] [F(n-4)]

可用矩陣快速冪 O(log n) 計算單項，但本題多查詢預計算更優。

複雜度分析

關鍵優化點

1. 預計算上界：題目說不超過 2005 位，實測 F(10000) 約 2000 位，N=10000 足夠
2. 只存非零長度：每個大整數記錄有效位長度，加法時只遍歷有效位
3. 輸出優化：從高位向低位找第一個非零，再輸出

測試樣例

Input:
100

Output:
4203968145672990846840663646

總結

HDU 1250 是大整數遞推入門題。Java/Python 選手優勢巨大（內建大整數）。C/C++ 需手寫大整數加法，考察基本功。競賽中遇到大整數遞推，優先考慮：1) 語言內建支持 2) 預計算 + 表格查詢 3) 矩陣快速冪 (單查詢大 n)。