Description
给定(n*n)的矩阵(A),求(A^k)
Input
第一行,(n),(k)
第(2)至(n+1)行,每行(n)个数,第(i+1)行第(j)个数表示矩阵第(i)行第(j)列的元素
Output
输出(A^k)
共(n)行,每行(n)个数,第(i)行第(j)个数表示矩阵第(i)行第(j)列的元素,每个元素模(10^9+7)
Solution
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int Mod=1e9+7;
int n;
long long k,ans[110][110],a[110][110],c[110][110];
long long mo(long long a,long long b)
{
return a+b>=Mod?a+b-Mod:a+b;
}
int main()
{
scanf("%d%lld",&n,&k);
for (int i=1;i<=n;i++) ans[i][i]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%lld",&a[i][j]);
while (k)
{
if (k&1)
{
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
c[i][j]=mo(c[i][j],ans[i][k]*a[k][j]%Mod);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
ans[i][j]=c[i][j];
}
k>>=1;
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
c[i][j]=mo(c[i][j],a[i][k]*a[k][j]%Mod);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
a[i][j]=c[i][j];
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<n;j++)
printf("%lld ",ans[i][j]);
printf("%lld
",ans[i][n]);
}
return 0;
}