G03 Luogu P3390【模板】矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P=1e9+7;
struct node
{
    LL a[110][110];
    node(){memset(a,0,sizeof a);}
};
int n;LL K;
node operator*(node A,node B)
{
    node C; 
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=n;k++)
                C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P;
    return C;
}
node qpow(node A,LL b)
{
    node C;for(int i=1;i<=n;i++)C.a[i][i]=1;
    for(;b;b>>=1,A=A*A)if(b&1)C=C*A;
    return C;
}
int main()
{
    scanf("%d%lld",&n,&K);
    node A;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&A.a[i][j]);
    A=qpow(A,K);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<n;j++)printf("%lld ",A.a[i][j]);
        printf("%lld\n",A.a[i][n]);
    }
    return 0;
}