疯子的算法总结(五) 矩阵乘法（矩阵快速幂）

墨蓝 2021-11-23 10:50 272阅读 0赞

学过线性代数的都知道矩阵的乘法，矩阵乘法条件第为一个矩阵的行数等与第二个矩阵的列数，乘法为第一个矩阵的第一行乘以第二个矩阵的第一列的对应元素的和作为结果矩阵的第一行第一列的元素。（详解参见线性代数）  
于是我们可以写出矩阵惩乘法的代码

struct JZ{
          int m[maxn][maxn];   };
    JZ muti(JZ a,JZ b)
    {
        
        JZ temp;
        memset(temp.m,0,sizeof(temp.m));
        for(int i=0;i<maxn;i++)
            for(int j=0;j<maxn;j++){
        
                for(int k=0;k<maxn;k++)
                {
        
                    temp.m[i][j]+=a.m[i][k]*b.m[k][j];
                }
                temp.m[i][j];
            }
        return temp;
    }

对于方阵我们能够自己乘自己，就是乘幂运算。  
我们参考快速幂，将数字的乘法换成矩阵的乘法，可以得出矩阵快速幂的代码；

#include<bits/stdc++.h>
    using namespace std;
    const int MOD=1e8+5;
    const int maxn=2; //定义方阵的阶数
    struct JZ{
          int m[maxn][maxn];   };//定义maxn阶方阵
    JZ muti(JZ a,JZ b,int mod);
    JZ quick_mod(JZ a,int k,int mod);
    int main()
    {
        
        JZ demo;
        JZ ans;
        int n;
        for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++) cin>>demo.m[i][j];
        while(cin>>n){
        
        ans=quick_mod(demo,n,MOD);
        for(int i=0;i<maxn;i++){
        
            for(int j=0;j<maxn;j++)
            cout<<ans.m[i][j]<<' ';
            cout<<endl;}
        }
    }
    JZ muti(JZ a,JZ b,int mod)
    {
        
        JZ temp;
        memset(temp.m,0,sizeof(temp.m));
        for(int i=0;i<maxn;i++)
            for(int j=0;j<maxn;j++){
        
                for(int k=0;k<maxn;k++)
                {
        
                    temp.m[i][j]+=(long long) a.m[i][k]*b.m[k][j]%mod;
                }
                temp.m[i][j]%=mod;
            }
        return temp;
    }
    JZ quick_mod(JZ a,int k,int mod)
    {
        
        JZ ans;
        for(int i=0;i<maxn;i++)
            for(int j=0;j<maxn;j++)
                ans.m[i][j]=(i==j);
        while(k)  {
        
        if(k &1)  ans =muti(ans,a,mod);
        a = muti(a,a,mod);
        k >>=1;
        }
        return ans;
    }

应用：矩阵快速幂求斐波那契数列。  
我们定义一个矩阵A  
|0 1|  
|1 1|  
定义F(0)=0,F(1)=1。  
构成矩阵F矩阵|0 1|  
A矩阵的N次幂，乘以F矩阵的第一项就是第N个斐波那契数列。  
证明：  
F矩阵乘以A矩阵代表将右侧元素给左侧，右侧元素等于右侧加左侧。矩阵的乘法满足结合律，所以F*X*X\*……N……*X = F (XX*X……\*X）  
所以定义不同的F矩阵可以得到不同的斐波那契数列。