利用“矩阵快速幂”实现的本题代码，可作为“矩阵快速幂”模板用

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=15;
const int MOD=1e8;
LL n,k;

struct Matrix {
    LL m[maxn][maxn];
    Matrix() { //Constructor in struct
        memset(m,0,sizeof m);
    }
};

Matrix a; //Input matrix
Matrix e; //Identity matrix

Matrix mul(Matrix a, Matrix b) {
    Matrix ans;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++)
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
    return ans;
}

Matrix fastPow(Matrix a,LL n) {
    Matrix ans=e;
    while(n) {
        if(n & 1) ans=mul(ans,a);
        a=mul(a,a);
        n>>=1;
    }
    return ans;
}

int main() {
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/

    cin>>n>>k;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cin>>a.m[i][j];
        }
    }

    //Identity matrix initialization
    for(int i=1; i<=n; i++) {
        e.m[i][i]=1;
    }

    Matrix t=fastPow(a,k);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(j!=n) cout<<t.m[i][j]%MOD<<" ";
            else cout<<t.m[i][j]%MOD<<endl;
        }
    }

    return 0;
}

/*
in:
2 2
9 8
9 3

out:
153 96
108 81
*/