新瓶陈酒 --- 矩阵快速幂

矩阵

//矩阵的定义
typedef struct Matrix{
    
    int r,c,matrix[MAXN][MAXN];
    Matrix(){
    
        r=c=0;
        memset(matrix,0,sizeof matrix);
    }
}Matrix;

//读入矩阵
void readMatrix(Matrix &n){
    
    cin>>n.r>>n.c;
    for(int i=1;i<=n.r;++i){
    
        for(int j=1;j<=n.c;++j)
            cin>>n.matrix[i][j];
    }
}

//打印输出矩阵
void printMatrix(Matrix n){
    
	cout<<n.r<<" "<<n.c;
    for(int i=1;i<=n.r;++i){
    
        for(int j=1;j<=n.c;++j)
            cout<<n.matrix[i][j]<<" ";
        cout<<endl;
    }
}

矩阵乘法

//不带取余的矩阵乘法
Matrix multiMatrix(Matrix a,Matrix b){
    
    Matrix c; c.r=a.r; c.c=b.c;
    for(int i=1;i<=a.r;++i)
        for(int j=1;j<=b.c;++j)
            for(int k=1;k<=a.c;++k)
                c.matrix[i][j]+=matrix.a[i][k]*b.matrix[k][j];
    return c;
}

矩阵快速幂

//带取余的矩阵乘法
Matrix multiMatrix(Matrix a,Matrix b,int mod){
    
    Matrix c;
    c.r=a.r;
    c.c=b.c;
    for(int i=1;i<=a.r;++i)
        for(int j=1;j<=b.c;++j)
            for(int k=1;k<=a.c;++k)
            	//和不带取余的矩阵乘法主要差距在这一语句上
                c.matrix[i][j]=(c.matrix[i][j]+(a.matrix[i][k]*b.matrix[k][j])%mod)%mod;
    return c;
}

//构造一个单位矩阵
Matrix initMatrix(int n){
    
    Matrix a;
    a.r=a.c=n;
    for(int i=1;i<=n;i++)a.matrix[i][i]=1;
    return a;
}

//矩阵快速幂其实和数字的快速幂没有本质区别，都是采用二分的思路
Matrix quickMultiMatrix(Matrix a,int n,int mod){
    
    Matrix ans=initMatrix(a.r);
    Matrix temp=a;
    while(n){
    
        if(n&1)ans=multiMatrix(ans,temp,mod);
        temp=multiMatrix(temp,temp,mod);
        n/=2;
    }
    return ans;
}