矩阵乘法+快速幂优化递推式

对于一个一维的递推式，如斐波那契数列：f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2), 如果想求解第n个元素，一般就是用O(n)复杂度来求解，但是这不是最优的

优化方法： 矩阵乘法+快速幂

首先可以用一个矩阵递推下一维，对斐波那契来说，这个矩阵就是：(1,1)(1,0). 那么我们想求第n个数，只要把这个矩阵乘n次就好了，到这里，复杂度还是O(n)。但是我们已经用了一个矩阵表示，要优化就很简单，只需要用快速幂就好，原理很简单，举个例子，计算2^100, 我们只需要计算2^50 * 2^50，然后不断二分，这样就能在logn的复杂度得到结果，代码如下：

//以斐波那契数列为例

#include<iostream>

#include<vector>

#define MOD 10000007

using namespace std;

typedef vector<long long> vec;

typedef vector<vec> mat;

//计算A*B

mat mul(mat &A,mat &B)

{

   mat C(A.size(),vec(B[0].size()));

   for(int i=0;i<A.size();i++)

       for(int k=0;k<B.size();k++)

           for(int j=0;j<B[0].size();j++)

               C[i][j]=(C[i][j]+A[i][k]*B[k][j]+MOD) % MOD;

   return C;

}

//计算A^n

mat pow(mat A,long long n)

{

   mat B(A.size(),vec(A.size()));

   for(int i=0;i<A.size();++i)

       B[i][i]=1;

   while(n>0)

    {

       if(n&1)

           B=mul(B,A);

       A=mul(A,A);

       n>>=1;

    }

   return B;

}

int main()

{

   long long n;

   cin>>n;

   mat A(2,vec(2));

   A[0][0]=1; A[0][1]=1;

   A[1][0]=1; A[1][1]=0;

   A=pow(A,n);

   cout<<A[1][0]<<endl;

}