题解 | #矩阵幂#快速幂，矩阵的定义、输出、乘法，矩阵快速幂

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

//例题6.12 矩阵幂
struct matrix{
    int data[10][10];
    int row,col;
    matrix(int r,int c):row(r),col(c){}
};

matrix mul(matrix x,matrix y){
    matrix ans=matrix(x.row,y.col);
    for(int i=0;i<x.row;i++){
        for(int j=0;j<y.col;j++){
            ans.data[i][j]=0;
            for(int k=0;k<x.col;k++){
                ans.data[i][j]+=x.data[i][k]*y.data[k][j];
            }
        }
    }
    return ans;
}

void printm(matrix x){
    for(int i=0;i<x.row;i++){
        for(int j=0;j<x.col;j++){
            printf("%d ",x.data[i][j]);
        }
        printf("\n");
    }
}

matrix mat_ksm(matrix x,int n){
    matrix total(x.row,x.col);
    for(int i=0;i<x.row;i++)
    for(int j=0;j<x.col;j++){
        if(i==j)total.data[i][j]=1;
        else total.data[i][j]=0;
    }
    matrix tmp=x;
    while(n!=0){
        if(n%2==1){
            total=mul(total,tmp);
        }
        tmp=mul(tmp,tmp);
        n/=2;
    }
    return total;
}

int main(){
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF){
        matrix input(n,n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>input.data[i][j];
            }
        }
        matrix output=mat_ksm(input,k);
        printm(output);
    }
    return 0;
}

另：快速幂的代码：

int kuaisumi(int x,int n){
    int ans=x;
    int total=1;
    while(n!=0){
        if(n%2==1){
            total*=ans;
        }
        ans=ans*ans;
        n=n/2;
    }
    return total;
}


//例题6.10 大数快速幂的后三位
int main(){
    int x;int n;
    cin>>x>>n;
    int ans=x;
    int total=1;
    while(n!=0){
        if(n%2==1){
            total*=ans;
            total%=1000;
        }
        ans=ans*ans;
        n=n/2;
        ans%=1000;
    }
    cout<<total<<endl;
    return 0;
}