这是 C 社算法团队的第一次活动。我们介绍了斐波那契数列的第n项求解方法,主要运用了矩阵快速幂算法。
斐波那契数列:
Fn=⎩⎨⎧0,1,Fn−2+Fn−1,n=0n=1n>1给定n,求Fn mod 109+7。
数据规模 | 内存限制 | 运行时间 |
---|
0≤n≤1019 | 64MB | 1.0s |
1019显然灭掉了所有用循环解决的想法。有没有比简单的O(n)更好一点的方法?用矩阵快速幂,可以达到O(logn)。观察到:
(Fn+1Fn+2)=(Fn+1Fn+Fn+1)=(0111)(FnFn+1)
这一步对于所有递推数列都是适用的,因此在有经验之后应该非常容易得到。一般地,对于Fn+2=aFn+bFn+1,有
(Fn+1Fn+2)=(Fn+1aFn+bFn+1)=(0a