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