P3390 【模板】矩阵快速幂

题目传送门

解题思路

这题就是矩阵乘法+快速幂模板
首先讲一下矩阵乘法
百度百科的解释

代码实现

	for(int o=1;o<=k;o++)//先枚举中间的数，更快 
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	   c[i][j]+=a[i][o]*b[o][j];

然后是快速幂
百度百科
就是为了方便求次方
代码实现

node ksm(node x,long long k)
{
   
	node y=x;//初值
	while(k)
	{
   
		if(k%2)y=x*y;//奇数
		x=x*x;
		k/=2;//除2
	}
	return y;
}

最后，这题就是将这两个算法结合

AC代码

#include<cstdio>
using namespace std;
long long n,k;
struct node//结构体
{
   
	long long oo[105][105];
}a;
node operator*(node x,node y)//更改“*”的定义，变为矩阵乘法
{
   
	node z;
	for(long long i=1;i<=n;i++)
	 for(long long j=1;j<=n;j++)
	  z.oo[i][j]=0;
	for(long long o=1;o<=n;o++)  
	 for(long long i=1;i<=n;i++)
	  for(long long j=1;j<=n;j++)
	   z.oo[i][j]=(z.oo[i][j]+x.oo[i][o]*y.oo[o][j])%1000000007;
	return z;
}
node ksm(node x,long long k)//快速幂
{
   
	node y=x;
	while(k)
	{
   
		if(k%2)y=x*y;
		x=x*x;
		k/=2;
	}
	return y;
}
int main()
{
   
	scanf("%lld%lld",&n,&k);
	for(long long i=1;i<=n;i++)
	 for(long long j=1;j<=n;j++)
	  scanf("%lld",&a.oo[i][j]);
	a=ksm(a,k-1);//快速幂，记住是k-1，因为有初值
	for(long long i=1;i<=n;i++,printf("\n"))
	 for(long long j=1;j<=n;j++)
	  printf("%lld ",a.oo[i][j]);
	return 0;
}

谢谢