nyoj_148_fibonacci数列(二)_矩阵快速幂
fibonacci数列(二)
时间限制： 1000 ms | 内存限制：65535 KB
难度： 3
In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
An alternative formula for the Fibonacci sequence is
Given an integer n, your goal is to compute the last 4 digits of Fn.
Hint
As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by
Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:
</dd> </dl>
0 9 1000000000 -1</dd> <dt> 样例输出 </dt> <dd>
0 34 6875</dd> <dt> 来源 </dt> <dd> POJ </dd> <dt> 上传者 </dt> <dd> hzyqazasdf </dd> <dd> 解题思路： </dd> <dd> 一下午就学了这一个算法，有很多细节总是花很长时间才理解。感觉自己学习算法效率好低啊。 </dd> <dd> 之前刚接触斐波那契数列，想找一个更高效的方法来求，当时看到了，却根本不懂。原来这就是矩阵快速幂。。。从此有了求斐波那契数列更好的方法 </dd> <dd> 既然整数求幂可以用快速幂来求，那么矩阵的幂同样也可以啊。 </dd> </dl>
#include <iostream> #include <cstdio> #include <cstring> #define mod 10000 using namespace std; struct matrix{ int m[2][2]; }; matrix base,ans; void init(int n){//只初始化base和ans(单位矩阵) memset(base.m,0,sizeof(base.m)); memset(ans.m,0,sizeof(ans.m)); for(int i=0;i<2;i++){ ans.m[i][i]=1; } base.m[0][0]=base.m[0][1]=base.m[1][0]=1; } matrix multi(matrix a,matrix b){ matrix t; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ t.m[i][j]=0; for(int k=0;k<2;k++){ t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%mod; } } } return t; } int fast_matrix(int n){ while(n){ if(n&1){ ans=multi(ans,base); } base=multi(base,base); n>>=1; } return ans.m[1][0]; } int main() { int n; while(~scanf("%d",&n) && n!=-1){ init(n); printf("%d\n",fast_matrix(n)); } return 0; }
