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

問題描述

斐波那契數列：F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂。給定 n (0 ≤ n ≤ 10⁹)，輸出 Fₙ 末四位（去前導零，全零輸出 0）。多測試用例，-1 結束。

矩陣形式

[Fₙ, Fₙ₋₁]ᵀ = Aⁿ⁻¹ [F₁, F₀]ᵀ，其中 A = [[1,1],[1,0]]。即 Aⁿ = [[Fₙ₊₁, Fₙ],[Fₙ, Fₙ₋₁]]。求 Fₙ 即求 Aⁿ 的 [1][0] 元素（0-based）。

快速冪算法

矩陣乘法結合律，可用二進制快速冪：

matrix pow(matrix a, long long n) {
    matrix res = identity;
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

模 10000 運算防止溢出。單次乘法 8 次乘加，log₂(10⁹) ≈ 30 步，極快。

代碼細節

• 結構體 `matrix` 含 int f[2][2]，重載 `operator*` 實現模乘。
• 主循環讀 n，-1 退出。初始化 A = [[1,1],[1,0]]，單位矩陣 I。
• 計算 Aⁿ，輸出 res.f[1][0]（即 Fₙ）。注意 n=0 時 A⁰=I，I[1][0]=0 正確。
• 輸出直接用 `%d`，自動去前導零；全零情況 0 正確輸出。

複雜度

每測試用例 O(log n) 矩陣乘法，常數極小。多測試用例總時間可忽略。

拓展：畢達哥拉斯周期

模 10000 下斐波那契數列週期為 15000（皮薩諾週期）。可預計算前 15000 項直接查表，但矩陣快速冪代碼更簡潔通用，無需記憶週期長度。

總結

本題是矩陣快速冪的模板題，考察線性遞推轉矩陣、模運算、快速冪模板。代碼簡短高效，是算法競賽必會技能。