矩阵乘法优化求斐波那契

不知道斐波那契数列是什么的自己去百度……

求斐波那契的第n项是一个老生常谈的问题，先送上一个O(n)的弱智算法……

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4     int n;
 5     cin>>n;
 6     if(n==1||n==2){
 7         cout<<1;
 8         return 0;
 9     }
10     int a=1,b=1,c;
11     for(int i=3;i<=n;i++){
12         c=a+b;
13         a=b;
14         b=c;
15     }
16     cout<<c;
17 }

这种方法求到10^7次方没问题，可是假如让求2^31-1之类的那就死菜了……所以我们需要优化！！！

首先先来介绍一下矩阵乘法

定义：设A为m*p的矩阵，B为p*n的矩阵，那么称m*n的矩阵C为矩阵A与B的乘积，记作C=AB，其中矩阵C中的第i行第j列元素可以表示为:(AB)_{i j} =a_i1b_1j+a_i2b_2j+……+a_ikb_kj

上面说的其实就是矩阵乘法的计算方式下面我们就需要构造一个合理的模板矩阵来对一个初始矩阵进行连乘得到我们要的答案

来针对斐波那契数列说一下我们可以构造模板矩阵来连续相乘因为矩阵乘法满足结合律，所以我们可以通过快速幂算出，最后在乘上初始的矩阵就好了。

代码如下：

#include<iostream>
#include<memory.h>
using namespace std;
//-----------------------
struct matrix{
    int m[3][3];
    int l,h;
    matrix(){memset(m,0,sizeof(m));}
}mdl,ans;//矩阵结构体
//mdl代表模板矩阵(需要做快速幂的矩阵) 
//ans代表答案(初始)矩阵 

matrix operator * (matrix a,matrix b){
    matrix c;
    c.l=b.l;c.h=a.h;
    for(int i=1;i<=c.h;i++){
        for(int j=1;j<=c.l;j++){
            for(int k=1;k<=a.l;k++){
                c.m[i][j]+=a.m[i][k]*b.m[k][j];
            }
        }
    }
    return c;
}//矩阵乘法
//-----------------------
matrix mat_qp(int x){//矩阵快速幂
    matrix res;
    res.l=mdl.l;res.h=mdl.h;
    for(int i=1;i<=2;i++)res.m[i][i]=1;
    while(x>0){
        if(x&1)res=res*mdl;
        mdl=mdl*mdl;
        x>>=1;
    }
    return res;
}
//------------------------
int n;
int main(){
    cin>>n;
    
    mdl.l=mdl.h=2;
    mdl.m[1][1]=mdl.m[1][2]=mdl.m[2][1]=1;
    //构造模板矩阵
    ans.l=1;ans.h=2;
    ans.m[1][1]=ans.m[2][1]=1;
    //构造初始矩阵 
    ans=mat_qp(n-2)*ans;
    cout<<ans.m[1][1]<<endl;
}

Time:O(logn)其实这种题最难想的就是模板矩阵了……