P3390

代码：：

#include<iostream>
#include<cstring>
using namespace std;
#define MN 110
#define ull unsigned long long
struct matrix
{
	ull n,m;
	ull a[MN][MN];
	matrix(ull N=0,ull M=0)
	{
		n=N;m=M;
		memset(a,0,sizeof(a));
	}
	matrix operator*(matrix const& b)
	{
		matrix c;
		c.n=n;c.m=b.m;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=b.m;j++)
		{
			ull sums=0;
			for(int k=1;k<=m;k++)
			sums+=a[i][k]*b.a[k][j]%1000000007;
			c.a[i][j]=sums%1000000007;
		}
		return c;
	}
	void array_to_matrix(int b[][100])
	{
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		a[i][j]=b[i][j];
	}
	friend istream& operator>>(istream& in,matrix& a)//已赋过n,m 
	{
		for(int i=1;i<=a.n;i++)
		for(int j=1;j<=a.m;j++)
		cin>>a.a[i][j];
		return in;
	}
	friend ostream& operator<<(ostream& out,matrix a)
	{
		for(int i=1;i<=a.n;i++)
		{
			for(int j=1;j<=a.m;j++)
			{
				cout<<a.a[i][j];
				if(j!=a.m)
				cout<<" ";
			}
			if(i!=a.n)
			cout<<endl;
		}
		return out;
	}
};
matrix make_I(int N)
{
	matrix ans;
	ans.n=ans.m=N;
	for(int i=1;i<=ans.n;i++)
	ans.a[i][i]=1;
	return ans;
}
matrix pows(matrix a,ull b)
{
	//cout<<"a:"<<endl<<a<<endl<<"b:"<<b<<endl;
	if(b==0) return make_I(a.n);
	if(b==1) return a;
	if(b%2==0) return pows((a*a),(b/2));
	if(b%2==1) return pows((a*a),(b/2))*a;
}
int main()
{
	int n,k;
	cin>>n>>k;
	matrix a(n,n);
	cin>>a;
	cout<<pows(a,k);
	return 0;
}