写的不错的博客：http://www.cnblogs.com/yan-boy/archive/2012/11/29/2795294.html
优点：根据数列递推式快速计算数列an的值（当n很大时）
步骤：由数列递推式构造矩阵，然后用矩阵快速幂计算矩阵的幂。
构造矩阵：对于an =x*an-1 +y*an-2 ,可以构造矩阵为：
[an ,an-1]=[an-1 ,an-2]*A
A=[x 1
y 0];
矩阵快速幂模板：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int MOD=10000; struct Matrix { ll a[2][2]; }A,res; Matrix multiply(Matrix x,Matrix y) { Matrix res; mem(res.a,0); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD; return res; } void qpow(int n) { while(n) { if(n&1)res=multiply(res,A); A=multiply(A,A); n=n>>1; } }
代码：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int MOD=10000; struct Matrix { ll a[2][2]; }A,res; Matrix multiply(Matrix x,Matrix y) { Matrix res; mem(res.a,0); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD; return res; } void qpow(int n) { while(n) { if(n&1)res=multiply(res,A); A=multiply(A,A); n=n>>1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; while(cin>>n) { if(n==-1)break; mem(res.a,0); for(int i=0;i<2;i++)res.a[i][i]=1; A.a[0][0]=1; A.a[0][1]=1; A.a[1][0]=1; A.a[1][1]=0; qpow(n); cout<<res.a[0][1]<<endl; } return 0; }
原文：http://www.cnblogs.com/widsom/p/7512690.html
