HDU ACM OJ 1005 數列週期：遞推關係與模 7 狀態壓縮說明

題目

f(1) = 1, f(2) = 1, f(n) = (A × f(n-1) + B × f(n-2)) mod 7，求 f(n)。

為什麼最多 49 個數就會出現週期？

• 每個數的範圍是 0~6（共 7 個可能）。
• 遞推關係只依賴「連續兩個數」，因此狀態為 (f(n-1), f(n-2))。
• 狀態總數最多 7 × 7 = 49 種。
• 根據抽屜原理，超過 49 個數後，一定會出現之前出現過的連續兩數狀態。
• 一旦狀態重複，之後的數列就會依照相同規律重複，形成週期。