收藏 
关注 给出一个N * N的矩阵，其中的元素均为正整数。求这个矩阵的M次方。由于M次方的计算结果太大，只需要输出每个元素Mod (10^9 + 7）的结果。
Input
第1行：2个数N和M，中间用空格分隔。N为矩阵的大小，M为M次方。(2 <= N <= 100, 1 <= M <= 10^9) 第2 - N + 1行：每行N个数，对应N * N矩阵中的1行。(0 <= N[i] <= 10^9)
Output
共N行，每行N个数，对应M次方Mod (10^9 + 7)的结果。
Input示例
2 3 1 1 1 1
Output示例
4 4 4 4
题解：矩阵快速幂用于解决运算非常多的计算，只要找到他们a（n）和a（n+1）的关系就可以推导出矩阵方程，然后套模板即可。
参考博客：打开链接
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long int
const int N=100;
long long tmp[N][N];
void multi(ll a[][N],ll b[][N],ll n,ll m) //矩阵运算
{
memset(tmp,0,sizeof(tmp));
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
for(int k=0;k<m;k++)
{
tmp[i][j]=((a[i][k]*b[k][j])%MOD+tmp[i][j])%MOD;
}
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
{
a[i][j]=tmp[i][j];
}
}
ll res[N][N];//存放结果的数组
void Pow(ll a[][N],ll n,ll m)
{
memset(res,0,sizeof res); //n是幂，m是矩阵大小
for(int i=0;i<m;i++) res[i][i]=1; //单位矩阵
while(n)
{
if(n%2==1)
{
multi(res,a,n,m);//res=res*a;复制直接在multi里面实现了；
}
multi(a,a,n,m);//a=a*a
n=n/2;
}
}
int main()
{
ll nn,mm;
scanf("%lld%lld",&nn,&mm);//nn为矩阵大小，mm为幂。
ll aa[100][100];
for(int i=0;i<nn;i++)
{
for(int j=0;j<nn;j++)
{
scanf("%lld",&aa[i][j]);
}
}
Pow(aa,mm,nn);
for(int i=0;i<nn;i++)
{
for(int j=0;j<nn;j++)
{
if(j==0)
printf("%lld",res[i][j]);
else
printf(" %lld",res[i][j]);
}
putchar('\n');
}
return 0;
} 
京公网安备 11010502036488号