POJ 3070 Fibonacci：矩陣快速冪求末四位

問題描述

求斐波那契數 F_n 最後 4 位（去前導零，全零輸出 0）。n ≤ 10⁹，多測試用例，以 -1 結束。

矩陣加速遞推

斐波那契遞推：[F_n, F_{n-1}]^T = M * [F_{n-1}, F_{n-2}]^T，其中
M = [[1,1],[1,0]]。

則 [F_n, F_{n-1}]^T = M^{n-1} * [F_1, F_0]^T = M^{n-1} * [1,0]^T。
故 F_n = (M^{n-1})_{0,0}。

快速冪模板

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

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

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

完整解題代碼

int main() {
    long long n;
    Mat M;
    M.a[0][0] = M.a[0][1] = M.a[1][0] = 1;
    M.a[1][1] = 0;
    
    while (cin >> n, n != -1) {
        if (n == 0) { cout << "0\n"; continue; }
        Mat R = mpow(M, n - 1);
        cout << R.a[0][0] % 10000 << "\n";
    }
    return 0;
}

關鍵細節

• 模數 10000，矩陣乘法中每步取模防溢出（int 足夠）。
• n=0 特判輸出 0。
• 單位矩陣對應 M^0，正確處理 n=1 情況（M^0 * [1,0]^T = [1,0]^T → F₁=1）。
• 避免矩陣乘法交換律錯誤：res = res * base 而非 base * res。

複雜度

• 矩陣乘法 O(2³)=O(1)。
• 快速冪 O(log n)。
• 總體極快。

總結

線性遞推轉矩陣快速冪是 O(log n) 求第 n 項的通用技巧。關鍵在於正確構造轉移矩陣與初始向量，並注意矩陣乘法不滿足交換律，快速冪中乘法順序固定為 res = res * base。