题解 | #矩阵幂#

借助快速幂的思想，多了一步：初始化为单位矩阵

#include<iostream>
using namespace std;

const int Maxn=10;
struct Matrix{
    int matrix[Maxn][Maxn];
    int row,col;
    Matrix(){};
    Matrix(int r,int c):row(r),col(c){};
};

void in_Matrix(Matrix &x){//输入矩阵
    for(int i=0;i<x.row;i++){
        for(int j=0;j<x.col;j++){
            scanf("%d",&x.matrix[i][j]);
        }
    }
}

void out_Matrix(Matrix &x){//输出矩阵
    for(int i=0;i<x.row;i++){
        for(int j=0;j<x.col;j++){
            if(j==0)printf("%d",x.matrix[i][j]);
            else printf(" %d",x.matrix[i][j]);
        }
        printf("\n");
    }
}
Matrix mul_Matrix(Matrix x,Matrix y){//矩阵乘法
    Matrix s(x.row,y.col);
    for(int i=0;i<x.row;i++){
        for(int j=0;j<y.row;j++){
            s.matrix[i][j]=0;
            for(int k=0;k<x.col;k++){
                s.matrix[i][j]+=x.matrix[i][k]*y.matrix[k][j];
            }
        }
    }
    return s;
}

Matrix exp_Matrix(Matrix x,int k){//快速幂
    Matrix s(x.row,x.col);
    for(int i=0;i<x.row;i++){//初始化为单位矩阵
        for(int j=0;j<x.col;j++){
            if(i==j)s.matrix[i][j]=1;
            else s.matrix[i][j]=0;
        }
    }
    while(k!=0){
        if(k%2==1){
            s=mul_Matrix(s,x);
        }
        k/=2;
        x=mul_Matrix(x,x);
    }
    return s;
}

int main(){
    int n,k;
    while(scanf("%d %d",&n,&k)!=EOF){
        Matrix x(n,n);
        in_Matrix(x);
        Matrix s=exp_Matrix(x,k);
        out_Matrix(s);
    }
    return 0;
}