主題
題目連結：
題目大意：
設第 x 項的費氏數列之值為 fib(x) 。
給定一正整數 n （1 ≦ n ≦ 10 ^ 5），代表有 n 筆測試資料。每筆測試資料佔一列，每列給定一正整數 x ，求 fib(fib(x)) 除以 M ＝ 1000000007 的餘數。
註：存在一 M' 值（M' ≦ 10 × M），使得 fib(fib(x) mod M') mod M ≡ fib(fib(x)) mod M ，其中「mod」代表取餘數。
範例輸入：
6
1
1
2
3
5
8
範例輸出：
1
1
1
1
5
10946
解題思維：
我們需要找到滿足 fib(x) ≡ fib(x ＋ kM') 且 fib(x ＋ 1) ≡ fib(x ＋ kM' ＋ 1) （mod M'）的 M' 值，才能使 fib(X mod M') mod M ≡ fib(X) mod M ，其中 X 即是題目的 fib(x) 值。
根據費氏數列的第 0 項 ＝ 0 以及第 1 項 ＝ 1 可以知道此 M' 值是費氏數列模 M 下的皮薩諾週期（Pisano Period）之長度。
設 X ＝ t ＋ kM' ，而 fib(t) 與 fib(t ＋ kM') 正好差了模 M 下的 k 個週期。因此 fib(t) 與 fib(t ＋ kM') 同餘。代入原本的 X 值即可得到 fib(fib(x) mod M') ≡ fib(fib(x)) （mod M）。
而皮薩諾週期的可由單純的迭代費氏數列而得（要 mod M）。第 0 項 ＝ 0 ，第 1 項 ＝ 1 ，迭代一次得第 1 項 、 第 2 項 ，迭代第二次得第 2 項、第 3 項……迭代到當第 M' 項 ＝ 0 、第 M' ＋ 1 項 ＝ 1 為止。此時的 M' 即是模 M 下的皮薩諾週期。
而用程式跑一下可得 M ＝ 1000000007 的皮薩諾週期之長度為 M' ＝ 2000000016 。
接著先用矩陣快速冪（如此題的作法）計算出 mod M' 後的 fib(x) 。接著再將此值代入一次矩陣快速冪求得最後模 M 下的 fib(fib(x)) 之值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
