藍橋杯 C 語言入門：費波納契數列模 10007 (動態規劃/迭代優化)

藍橋杯 入門訓練 - Fibonacci 數列模 10007：滾動陣列與模運算分配律

題目：F₁ = F₂ = 1，Fₙ = Fₙ₋₁ + Fₙ₋₂ (n ≥ 3)。輸入 n (1 ≤ n ≤ 1,000,000)，輸出 Fₙ mod 10007。
樣例：10 → 55，22 → 7704。

核心觀察

1. Fₙ 指數級增長，n=1,000,000 時位數超過 20 萬位，無法直接儲存。
2. 模運算分配律：(a + b) mod m = (a mod m + b mod m) mod m。
   → 迭代過程中每步取模，數值永遠在 [0, 10006] 範圍內，完全避免大數問題。
3. 只需保留前兩項，空間可優化為 O(1) (滾動變數)。

優化演算法：O(n) 時間、O(1) 空間

#include 
#define MOD 10007

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    if (n <= 2) { printf("1\n"); return 0; }

    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = (a + b) % MOD;
        a = b;
        b = c;
    }
    printf("%d\n", b);
    return 0;
}

進階：矩陣快速冪 O(log n) (選讀)

若 n 擴大至 10¹⁸，需用矩陣快速冪：

[Fₙ  ]   = [1 1]^(n-2) * [F₂]
[Fₙ₋₁]     [1 0]          [F₁]

配合模運算，同樣適用。但本題 n ≤ 1e6，線性迭代完全足夠 (約 10⁶ 次運算，< 10ms)。

常見錯誤與避坑

關鍵知識點總結

1. 模運算分配律 是解決大數遞推取模問題的通用鑰匙。
2. 滾動陣列/變數 將空間從 O(n) 降為 O(1)，避免棧溢位與記憶體浪費。
3. 邊界條件 (n=1,2) 必須額外處理。
4. 型別選擇：int 足夠容納模 10007 後的中間結果。

此題完美展示「數學性質 + 空間優化」如何將看似需要大數運算的問題轉化為極簡高效的解法。