比赛 |
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(){;}