题解 | #矩阵幂#

#include<iostream>
#include<vector>
using namespace std;

//矩阵快速幂

class Matrix{
    public:
    int row,col;
    vector<vector<int>> datas;

    Matrix(int row,int col):row(row),col(col),datas(row,vector<int>(col,0)){
    
    }
};

Matrix mul(Matrix a,Matrix b){
    int row=a.row;
    int col=b.col;
    // vector<vector<int>> datas(row,vector<int>(col,0));
    Matrix res(row,col);
    for(int i=0;i<a.row;i++){
        for(int j=0;j<b.col;j++){
            for(int k=0;k<a.col;k++){
                res.datas[i][j]+=a.datas[i][k]*b.datas[k][j];
            }
        }
    }

    return res;
}

void print_matrix(Matrix x){
    for(int i=0;i<x.row;i++){
        for(int j=0;j<x.col;j++){
            cout<<x.datas[i][j]<<" ";
        }
        cout<<endl;
    }
}

Matrix fast_mul_matrix(Matrix a,int k){
    Matrix ans(a.row,a.col);
    for(int i=0;i<ans.row;i++){
        for(int j=0;j<ans.col;j++){
            if(i==j){
                ans.datas[i][j]=1;
            }
        }
    }
    while(k){
        if(k&1){
            ans=mul(a,ans);
        }
        a=mul(a,a);
        k>>=1;
    }
    return ans;
}

int main(){
    int n,k;
    while(cin>>n>>k){
        Matrix x(n,n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>x.datas[i][j];
            }
        }
        x=fast_mul_matrix(x,k);
        print_matrix(x);
    }
}