tioj 1757 Ch2. Section 2. 危險的樓梯間

今天遇見了一個我一直以為我不會遇見的東西


-> 循環節


先來證明費氏數列擁有循環節好了


餘數系：A = { 0, 1, 2, 3, ... k-1 } (mod k)


設定{ ( x, y ) , x 屬於 A 且 y 屬於 A }，有k*k種組合


所以在 k^2 項之內一定會出現重複


而且 Fn = Fn-1 + Fn-2


所以當( i, i+1 ) 和 ( j, j+1 ) 一樣時，i+2 = j+2 且 i-1 = j-1


意味著每距離 j-i ，就會出現跟自己一樣的


因此費氏數列有循環節。


至於這個距離，據說是沒有辦法計算出來的，


你可以直接假定初始的兩項，再 dp 跑過去


找到跟初始一樣的兩項即找到距離


這提用矩陣累乘配合循環節，即可成功AC囉！


http://codepad.org/uDwR2UAT