用矩阵表示递推公式是一个非常方便的方法，可以在O（log（n））的时间复杂度里面求解f（n），一般来说，递推项的系数要是常数或者能转化为常数。

情形1：F(n) = a₁F(n - 1) + a₂F(n - 2) + a₃F(n - 3) + … + a_kF(n - k)

观察上式可以得出下面等价方程组

     很明显可以构造一个矩阵

                                                                       

例题部分：

1. http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1752

构造矩阵为

将左边的矩阵乘n-1次 #include <iostream> using namespace std; typedef long long llt; const int Cube_SIZE = 3;///矩阵大小 struct Cube{ llt mat[Cube_SIZE][Cube_SIZE]; }; //单位矩阵 Cube _UnitCube = { 1, 0, 0, 0, 1, 0, 0, 0, 1 }; ///矩阵乘机 Cube _Multiply(Cube A,Cube B,llt mod){ Cube _tmpCube; for (int i = 0;i < Cube_SIZE;++i) for (int j = 0;j < Cube_SIZE;++j){ _tmpCube.mat[i][j] = 0; for (int k = 0;k < Cube_SIZE;++k){ _tmpCube.mat[i][j] += A.mat[i][k]*B.mat[k][j]; _tmpCube.mat[i][j] %= mod; } } return _tmpCube; } ///矩阵快速幂 Cube power_Cube(Cube A,llt n,llt mod) //矩阵快速幂 { Cube _tmpCube = _UnitCube; while(n){ if(n & 1) _tmpCube = _Multiply(_tmpCube, A ,mod); A = _Multiply(A, A, mod); n >>= 1; } return _tmpCube; } int main(){ int t;cin>>t; Cube tmp,arr; llt n,x1,a,b,MOD; while (t--){ cin>>x1>>a>>b>>MOD>>n; arr.mat[0][0] = a;arr.mat[0][1] = b;arr.mat[0][2] = 1; arr.mat[1][0] = 0;arr.mat[1][1] = 1;arr.mat[1][2] = 0; arr.mat[2][0] = 0;arr.mat[2][1] = 0;arr.mat[2][2] = 1; tmp.mat[0][0] = x1;tmp.mat[0][1] = 0;tmp.mat[0][2] = 0; tmp.mat[1][0] = 1; tmp.mat[1][1] = 0;tmp.mat[1][2] = 0; tmp.mat[2][0] = 1; tmp.mat[2][1] = 0;tmp.mat[2][2] = 0; arr = power_Cube(arr,n-1,MOD); arr = _Multiply(arr,tmp,MOD); llt ans = arr.mat[0][0]%MOD; cout <<ans<<endl; } return 0; }

2. http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1769

题目是计算非波拉契数列，n非常大，所以用矩阵快速幂 构造相当简单 #include <iostream> using namespace std; typedef long long llt; const int MOD = 1000000007; const int Cube_SIZE = 2;///矩阵大小 struct Cube{ llt mat[Cube_SIZE][Cube_SIZE]; }; //单位矩阵 Cube _UnitCube = { 1, 0, 0, 1, }; ///矩阵乘机 Cube _Multiply(Cube A,Cube B,llt mod){ Cube _tmpCube; for (int i = 0;i < Cube_SIZE;++i) for (int j = 0;j < Cube_SIZE;++j){ _tmpCube.mat[i][j] = 0; for (int k = 0;k < Cube_SIZE;++k){ _tmpCube.mat[i][j] += A.mat[i][k]*B.mat[k][j]; _tmpCube.mat[i][j] %= mod; } } return _tmpCube; } ///矩阵快速幂 Cube power_Cube(Cube A,llt n,llt mod) //矩阵快速幂 { Cube _tmpCube = _UnitCube; while(n){ if(n & 1) _tmpCube = _Multiply(_tmpCube, A ,mod); A = _Multiply(A, A, mod); n >>= 1; } return _tmpCube; } int main(){ Cube arr; llt n,hp1,hp2,hp3; while (cin>>hp1>>hp2>>hp3>>n){ if (n == 0){ cout <<hp1+hp2+hp3<<endl; continue; } llt ans = 0; arr.mat[0][0] = 0;arr.mat[0][1] = 1; arr.mat[1][0] = 1;arr.mat[1][1] = 1; arr = power_Cube(arr,n-1,MOD); ans += arr.mat[1][0] * (hp3-hp2) + arr.mat[1][1] * hp2; ans %= MOD; ans += arr.mat[1][0] * hp2 + arr.mat[1][1] * hp3; ans %= MOD; ans += arr.mat[1][0] * hp3 + arr.mat[1][1] * (hp2+hp3); ans %= MOD; cout <<ans<<endl; } return 0; }

3.http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10188

A Simple Math ProblemTime Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KBTotal submit users: 4, Accepted users: 3Problem 10188 : No special judgementProblem description  Lele now is thinking about a simple function f(x). If x < 10 f(x) = x. If x >= 10 f(x) = a₀ * f(x-1) + a₁ * f(x-2) + a₂ * f(x-3) + …… + a₉ * f(x-10); And a_i(0<=i<=9) can only be 0 or 1 . Now, I will give a₀ ~ a₉ and two positive integers k and m ,and could you help Lele to caculate f(k)%m. Input  The problem contains mutiple test cases.Please process to the end of file. In each case, there will be two lines. In the first line , there are two positive integers k and m. ( k<2*10⁹ , m < 10⁴ ) In the second line , there are ten integers represent a₀ ~ a₉. Output  For each case, output f(k) % m in one line.Sample Input 10 9999 1 1 1 1 1 1 1 1 1 1 20 500 1 0 1 0 1 0 1 0 1 0 Sample Output 45 104 情形一直接套公式 #include <iostream> using namespace std; typedef long long llt; const int Cube_SIZE = 10;///矩阵大小 struct Cube{ llt mat[Cube_SIZE][Cube_SIZE]; }; //单位矩阵 Cube _UnitCube = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, }; Cube tmp = { 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; ///矩阵乘机 Cube _Multiply(Cube A,Cube B,llt mod){ Cube _tmpCube; for (int i = 0;i < Cube_SIZE;++i) for (int j = 0;j < Cube_SIZE;++j){ _tmpCube.mat[i][j] = 0; for (int k = 0;k < Cube_SIZE;++k){ _tmpCube.mat[i][j] += A.mat[i][k]*B.mat[k][j]; _tmpCube.mat[i][j] %= mod; } } return _tmpCube; } ///矩阵快速幂 Cube power_Cube(Cube A,llt n,llt mod) //矩阵快速幂 { Cube _tmpCube = _UnitCube; while(n){ if(n & 1) _tmpCube = _Multiply(_tmpCube, A ,mod); A = _Multiply(A, A, mod); n >>= 1; } return _tmpCube; } int main(){ Cube arr; llt k,MOD; while (cin>>k>>MOD){ for (int i = 0;i < 10;++i){ cin>>tmp.mat[i][0]; } arr = power_Cube(tmp,k - 9LL,MOD); llt ans = 0; for (int i = 0;i < 10;++i){ ans += (10-i-1) * arr.mat[i][0]; ans %= MOD; } cout <<ans<<endl; } return 0; }

部分参考自：

http://wenku.baidu.com/link?url=b7uA6oQcOQmGmxIgHJq3vvE7NMWo1dzV9oTUCuEcqq1A5lO9L-76US3W8S7W4mfA_s5bMfKa5qDDSTTjq6n2lFPZDhMhba_iES8i_nbnxpe

http://luowei828.blog.163.com/blog/static/31031204201110133125750/