可以先推算一下,会发现m0,m1,m2,m3等为方阵的乘幂,其第1行第2列就是Fibonacci数列的项,关键是如何求矩阵的乘幂呢?
分奇数幂和偶数幂两种情况
A(2)^n因为方阵的乘法有结合律,所以A(2)^n=A(2)^(n/2)*A(2)^(n/2),不妨设n是偶数
所以求A(n)就可以化成求A(n/2)并作一次乘法,所以递归方程是:A(n)=A(n/2)^2
但是如果n为奇数,可以A(n)=A((n-1)/2) * A((n+1)/2或者A(n)=A((n-1)/2)^2 * A(1)
关于矩阵的乘幂运算也可以如下运算,用于POJ3744中:
分享到:
相关推荐
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
北大pku poj 3070 Fibonacci解题报告源代码 - acm解题报告
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems....
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
因为自己对递归还是不太熟练,于是做POJ1753的时候就很吃力,就是翻棋子直到棋盘上所有棋子的颜色一样为止,求最少翻多少次,方法是枚举递归。然后就打算先做另一道递归的题(从数组中取出n个元素的组合),但是同样...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj3233的代码,利用了面向对象的编程,是复习C++知识的好例子
poj大学c语言的作业及参考答案
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等