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

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;
}