POJ 3070 Fibonacci：矩陣快速冪求大數斐波那契

問題描述

輸入 n（≤ 10^9），求 F_n 模 10000，其中 F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}。輸入 -1 結束。

解題思路

利用矩陣快速冪：[F_n, F_{n-1}]^T = A^n * [F_1, F_0]^T，其中 A = [[1,1],[1,0]]。對 n 進行二進制分解，預先計算 A^(2^k) 並累乘。模 10000 運算防止溢出。

代碼實現 (C++)

#include 
using namespace std;
const int MOD = 10000;
struct Mat { int a[2][2]; };
Mat mul(Mat x, Mat y) {
    Mat r; memset(r.a, 0, sizeof(r.a));
    for (int i = 0; i < 2; ++i)
        for (int k = 0; k < 2; ++k)
            for (int j = 0; j < 2; ++j)
                r.a[i][j] = (r.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
    return r;
}
Mat mpow(Mat base, long long exp) {
    Mat res; memset(res.a, 0, sizeof(res.a));
    res.a[0][0] = res.a[1][1] = 1;
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}
int main() {
    long long n;
    Mat A; A.a[0][0]=1; A.a[0][1]=1; A.a[1][0]=1; A.a[1][1]=0;
    while (cin >> n && n != -1) {
        if (n == 0) { cout << 0 << endl; continue; }
        Mat ans = mpow(A, n-1);
        cout << ans.a[0][0] % MOD << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(log n) 矩陣乘法常數次。
• 空間複雜度：O(1)。

總結

矩陣快速冪是求線性遞推數列通項的標準方法，代碼簡短高效。注意 n=0 情況單獨處理，模運算在乘法中及時取模。