比赛 201712练习 评测结果 AAAAAAAAAA
题目名称 矩阵幂之和 最终得分 100
用户昵称 サイタマ 运行时间 0.941 s
代码语言 C++ 内存使用 0.34 MiB
提交时间 2018-01-07 10:43:19
显示代码纯文本
#include<fstream>
#include<cstring>
#define ll long long
using namespace std;
ifstream cin("matrix_sum.in");
ofstream cout("matrix_sum.out");
ll n,k,m,i,j;
ll mul(ll a, ll b)
{
	return (ll)(a*b - (ll)(a/(long double)m*b+1e-6)*m + m)%m;
}
class matrix
{public:
	ll a[31][31];
	void clear()
	{
		memset(a,0,sizeof(a));
		return;
	}
	matrix operator * (const matrix& x)const
	{
		matrix b;
		b.clear();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				for(int k=1;k<=n;k++)
				{
					b.a[i][j]+=mul(a[i][k],x.a[k][j]);
					b.a[i][j]=b.a[i][j]>=m?b.a[i][j]-m:b.a[i][j];
				}
		return b;
	}
	matrix operator + (const matrix& x)const
	{
		matrix b;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				b.a[i][j]=a[i][j]+x.a[i][j];
				b.a[i][j]=b.a[i][j]>=m?b.a[i][j]-m:b.a[i][j];
			}
		return b;
	}
}A,F,x,y;
int lyh()
{
	cin>>n>>k>>m;
	A.clear();
	F.clear();
	x.clear();
	y.clear();
	for(i=1;i<=n;i++)
	{
		x.a[i][i]=1;
		for(j=1;j<=n;j++)
		{
			cin>>A.a[i][j];
			A.a[i][j]%=m;
		}
	}
	y=A;
	while(k)
	{
		if(k&1)
		{
			F=F+x*y;
			x=x*A;
		}
		y=y+y*A;
		A=A*A;
		k>>=1;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++)
			cout<<F.a[i][j]<<' ';
		cout<<endl;
	}
	cin.close();
	cout.close();
	return 0;
}
int Main=lyh();
int main(){;}