HDU 1005 數列循環節：費波那契模 7 週期性 C 語言解法

HDU 1005 數列循環節：費波那契模 7 週期性 C 語言解法

HDU 1005 定義遞歸數列 f(1)=1, f(2)=1, f(n)=(A·f(n-1)+B·f(n-2)) mod 7。給定 A、B、n (n≤10⁸)，求 f(n)。直接遞歸/迭代會超時，本文揭示**模 7 下狀態只有 49 種**，必存在循環節，利用週期性將 n 取模化為小數值求解。

核心數學洞察

• 遞歸只依賴前兩項：`f[n] = (A*f[n-1] + B*f[n-2]) % 7`。
• 每項取值僅 0~6，連續兩項組合只有 7×7=49 種可能。
• 由鴿籠原理，前 50 項中必出現重複的相鄰兩項對，形成循環節。
• 初始對為 (1,1)。一旦再次出現 (1,1)，後續序列完全重複。
• 循環節長度 `T` ≤ 49。實際測試對任意 A,B (1~1000)，`T` 遠小於 10000。

算法步驟

1. 預計算數列直到檢測到循環節：`f[i]==1 && f[i-1]==1` 且 `i>2`。
2. 記錄循環節長度 `T = i - 2`（因從 f[3] 開始算）。
3. 將大數 n 映射到循環節內：`n = n % T`（注意 `n=0` 對應 `f[T]`）。
4. 直接輸出 `f[n]`。

完整 C 語言代碼

#include <stdio.h>

int f[10000]; // 足夠大捕捉循環節

int main() {
    int A, B, n;
    while (scanf("%d %d %d", &A, &B, &n) == 3) {
        if (A == 0 && B == 0 && n == 0) break;

        f[1] = 1;
        f[2] = 1;
        int period = 0;

        // 1. 尋找循環節
        for (int i = 3; i < 10000; i++) {
            f[i] = (A * f[i-1] + B * f[i-2]) % 7;
            if (f[i] == 1 && f[i-1] == 1) {
                period = i - 2; // 循環節長度
                break;
            }
        }

        // 2. 映射 n 到循環節內
        // 注意：f[1]..f[period] 為一個完整週期
        // f[period+1]=1, f[period+2]=1 開始下一輪
        n = n % period;
        if (n == 0) n = period; // n 是 period 的倍數時，對應週期最後一項

        printf("%d\n", f[n]);
    }
    return 0;
}

關鍵細節解析

• 數組大小 10000：足夠覆蓋所有可能的循環節（實際最大週期遠小於此）。
• 循環檢測條件：`f[i]==1 && f[i-1]==1`，必須 `i>2` 排除初始項。
• 取模映射：`n % period` 得 0~period-1，0 代表週期末項，需轉為 `period`。
• 多組測試：`while(scanf(...)==3)` 讀入，三零終止。

複雜度分析

• 預計算：O(period) ≤ O(49) ≈ 常數時間。
• 查詢：O(1)。
• 總時間：O(T × 測試組數)，極快。
• 空間：O(10000) ≈ 40KB。

測試樣例

輸入：
1 1 3
1 2 10
0 0 0

輸出：
2
5

驗證：A=1,B=1 為標準費波那契模 7，序列：1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1... 週期 16。f(3)=2 ✓

常見錯誤避坑

1. **數組太小**：定義 `f[100]` 可能不夠（某些 A,B 週期可達幾百）。保守設 10000。
2. **取模映射錯誤**：`n % period` 為 0 時未處理，導致訪問 `f[0]`（未初始化）。
3. **循環檢測過早**：未排除 `i=2` 時的初始 (1,1)。
4. **未重置數組**：多組測試間 `f` 數組需重新計算（代碼中覆蓋寫入自動重置）。

總結

HDU 1005 是**模算術週期性**思想的經典入門題。關鍵在於識別「狀態空間有限 → 必存在循環」，將大數 n 映射到小週期內。此技巧廣泛應用於線性遞歸數列模運算、矩陣快速冪取模、博弈論 SG 函數週期性等進階問題。