传送门
这题的传统做法应该是矩阵乘吧，下面说下思路:
首先你应该知道快速乘幂，如果不知道的，请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,可能是我矩阵写搓了。。。