题目背景
矩阵快速幂
题目描述
给定n*n的矩阵A，求A^k
输入输出格式
输入格式：
第一行，n,k
第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素
输出格式：
输出A^k
共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7
输入输出样例
输入样例#1：
2 1
1 1
1 1
输出样例#1：
1 1
1 1
说明
n<=100, k<=10^12, |矩阵元素|<=1000 算法：矩阵快速幂
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll x[][];
ll ans[][];
ll dx[][];
const int p=1e9+;
inline void anscf(int n)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dx[i][j]=ans[i][j],ans[i][j]=; for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
ans[i][j]=(ans[i][j]+(x[i][k]*dx[k][j])%p)%p;
}
inline void xcf(int n)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dx[i][j]=x[i][j],x[i][j]=; for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
x[i][j]=(x[i][j]+(dx[i][k]*dx[k][j])%p)%p;
}
inline void fastpow(ll n,ll w)
{
while(w)
{
if(w%==) anscf(n);
w/=;
xcf(n);
}
}
int main()
{
ll n,k;
scanf("%lld%lld",&n,&k);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&x[i][j]),ans[i][j]=x[i][j];
fastpow(n,k-);
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
printf("%lld ",ans[i][j]);
puts("");
}
}