题解 | 矩阵幂

#include <stdio.h>
typedef struct {
    int a[10][10];
    int r,c;
}np;
np mul(np x,np y){//矩阵乘法
    np z;
    z.r=x.r;
    z.c=y.c;
    for(int i=0;i<x.r;i++){
        for(int j=0;j<x.r;j++){
            z.a[i][j]=0;
            for(int k=0;k<x.c;k++)
                z.a[i][j]+=x.a[i][k]*y.a[k][j];
        }
    }
    return z;
}
void print(np x){
    for(int i=0;i<x.r;i++){
        for (int j=0; j<x.c; j++) {
            if(j!=0)
                printf(" ");
            printf("%d",x.a[i][j]);
        }
    printf("\n");
    }
}

np Exp(np z,int k){
    np x;
    x.c=z.c;
    x.r=z.r;
    for(int i=0;i<z.r;i++)
        for(int j=0;j<z.c;j++)
            if(i==j)
                x.a[i][j]=1;
            else
                x.a[i][j]=0;
    while(k){
        if(k%2==1)
            x=mul(x,z);
        k/=2;
        z=mul(z, z);
    }
    return x;
}

int main() {
    int n,k;
    while(scanf("%d %d",&n,&k)!=EOF){
        np x;
        x.c=n;
        x.r=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&x.a[i][j]);
        np t;
        t=Exp(x,k);
        print(t);
    }
    return 0;
}