比赛 201712练习 评测结果 AAAAAAAAAA
题目名称 矩阵幂之和 最终得分 100
用户昵称 烟雨 运行时间 0.942 s
代码语言 C++ 内存使用 0.25 MiB
提交时间 2018-01-08 19:49:45
显示代码纯文本
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll n,k,m;
ll op(ll a,ll b)
{
	return (ll)(a*b-(ll)(a/(long double)m*b+1e-6)*m+m)%m;
}
struct node
{
	ll s[31][31];
	void clear(){memset(s,0,sizeof(s));}
	node operator * (const node& x)const
	{
		node t;
		t.clear();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=n;k++)
				{
					t.s[i][j]+=op(s[i][k],x.s[k][j]);
					t.s[i][j]=t.s[i][j]>=m?t.s[i][j]-m:t.s[i][j];
				}
			}
		}
		return t;
	}
	node operator + (const node& x)const
	{
		node t;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				t.s[i][j]=s[i][j]+x.s[i][j];
				t.s[i][j]=t.s[i][j]>=m?t.s[i][j]-m:t.s[i][j];
			}
		}
		return t;
	}
}ans,x,y,u;
int LL()
{
	freopen ("matrix_sum.in","r",stdin);
	freopen ("matrix_sum.out","w",stdout);
	scanf("%lld%lld%lld",&n,&k,&m);
	ans.clear();x.clear();y.clear();u.clear();
	for(int i=1;i<=n;i++)
	{
		x.s[i][i]=1;
		for(int j=1;j<=n;j++)
		{
			scanf("%lld",&u.s[i][j]);
			u.s[i][j]%=m;
		}
	}
	y=u;
	while(k)
	{
		if(k&1)
		{
			ans=ans+x*y;
			x=x*u;
		}
		y=y+y*u;
		u=u*u;
		k>>=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			printf("%lld ",ans.s[i][j]);
		}
		printf("\n");
	}
	return 0;
}
int work=LL();
int main(){;}