原题

P3390 【模板】矩阵快速幂

10点全WA

以下为我的代码

#include<bits/stdc++.h>
using namespace std;
int a[101][101],b[101][101],ans[101][101],f[101][101],n,x;
void jz()//底数平方 
{	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
 	{	for(int j=1;j<=n;j++)
   		{	for(int k=1;k<=n;k++)
     		{	b[i][j]+=a[i][k]*a[k][j]%1000000007;
     		}
   		}
 	}
	 for(int i=1;i<=n;i++)
 	 {	for(int j=1;j<=n;j++)
 	 	{	a[i][j]=b[i][j]%1000000007;
		}
	 }
 	return;
}
void jz2()//当指数为奇数，用ans乘底数记录 
{	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
 	{	for(int j=1;j<=n;j++)
   		{	for(int k=1;k<=n;k++)
     		{	b[i][j]+=ans[i][k]*a[k][j]%1000000007;
     		}
   		}
 	}
	 for(int i=1;i<=n;i++)
 	 {	for(int j=1;j<=n;j++)
 	 	{	ans[i][j]=b[i][j]%1000000007;
		}
	 }
 	return;
}
void pow()
{	for(int i=1;i<=n;i++)
  	{	for(int j=1;j<=n;j++)
  		{	ans[i][j]=0;
		}
	}
   for(int i=1;i<=n;i++)
	{	ans[i][i]=1;
	}//构造一个主对角线都是一的正方形 
	while(x)//快速幂 
 	{	if(x%2)
	 	{	jz2();
 		}
 		x/=2;
 		jz(); 
 	}
 	return;
}
int main()
{	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++)
 	{	for(int j=1;j<=n;j++)
 		{	scanf("%d",&a[i][j]);
		}
	}
 	pow();
 	for(int i=1;i<=n;i++)
 	{	for(int j=1;j<=n;j++)
     	{	if(j==n)
     		{	cout<<ans[i][j]%1000000007;
			}
	 		else
	 		{	cout<<ans[i][j]%1000000007<<" ";
			}
	 	}
     	cout<<endl;
 	}
  	return 0;
}