POJ 3070 Fibonacci 完整解析

求第 N 個費波那契數模 10000，N ≤ 10⁹。多測資，N=-1 結束。輸出去除前導零（全零輸出 0）。

矩陣快速冪

[F(n), F(n-1)]^T = M^(n-1) × [F(1), F(0)]^T，其中
M = [[1,1],[1,0]]。
利用冪的結合律，O(log N) 計算 M^n。

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10000;

struct Matrix {
    int a[2][2];
    Matrix(bool ident = false) {
        memset(a, 0, sizeof(a));
        if (ident) a[0][0] = a[1][1] = 1;
    }
};

Matrix mul(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
    return C;
}

Matrix pow(Matrix base, long long exp) {
    Matrix res(true); // 單位矩陣
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    Matrix M;
    M.a[0][0] = M.a[0][1] = M.a[1][0] = 1;
    M.a[1][1] = 0;
    
    long long n;
    while (cin >> n, n != -1) {
        if (n == 0) { cout << 0 << '\n'; continue; }
        Matrix R = pow(M, n);
        cout << R.a[0][1] << '\n'; // F(n) = M^n[0][1]
    }
    return 0;
}

關鍵點總結

• 矩陣冪定義：M^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
• 模運算融合：乘法過程中每步取模，防溢位
• N=0 特判：M^0 = I，F(0)=0
• 輸出格式：直接輸出整數自動去除前導零（C++ 默認行為）
• 複雜度：O(log N) 每測資，極快