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