傳送門
這題的傳統做法應該是矩陣乘吧，下面說下思路:
首先你應該知道快速乘冪，如果不知道的，請google之。如果知道了快速乘冪，好這題你已經做了一大半了，剩下的就是把最小單元從數改成矩陣而已。也就是把快速乘冪中數改成矩陣就行了。然后剩下的就是計算機的事了，你可以等著OJ判了，不久就會返回Accept。恭喜你，如果不是的話，那么中間還有一些東西沒處理好，比如說最后結果到底是矩陣的那個元素，還有中間別忘了求余。其他的應該沒問題了，完事收工了。
第二種思路，同樣的log(n),不過不用矩陣，而是靠遞推出來的公式進行運算的。介紹請看這
然后第二種思路就出來了，不過中間可能理解有點難度，尤其是介紹的那里的t(m),至少我看的不是很懂，不過我理解的是這樣的，用個數做例子吧比如說n=30。那么化成二進制后變成11110,那么進行第k次之后,算F[30]---->F[15],F[16]---->F[7],F[8]---->F[3],F[4]----->F[1],F[2].現在我們反過來看如果要求F[30]，就得求F[15]和F[16],同時可以得到F[31],我們知道30化成二進制的最后一位是0,也就是偶數,由所給文章的推導式可得設這個偶數為2*m,那么我們是要算F[2*m]和F[2*m+1],下一步我們要算15和16,我們知道是要算F[7]和F[8],(15=2*7+1,16=2*7+2)15化成二進制后末位是1,也就是奇數,設為2*m+1,那么是由F[m]和F[m+1]得到，同時可以得到F[2*m+2],然后后面的分析和這個一樣的，于是就有了所給文章的那段代碼。語言不是很易懂，實在不懂就自己化成二進制慢慢想吧。
再啰嗦句:我用矩陣16MS,用后面的方法0MS,可能是我矩陣寫搓了。。。