比赛 |
201712练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
矩阵幂之和 |
最终得分 |
100 |
用户昵称 |
胡嘉兴 |
运行时间 |
1.064 s |
代码语言 |
C++ |
内存使用 |
0.32 MiB |
提交时间 |
2017-12-27 14:29:39 |
显示代码纯文本
#include<bits/stdc++.h>
#define N 37
#define ll long long
using namespace std;
ll n, m;
ll mul(ll a, ll b)
{
return (ll)(a*b - (ll)(a/(long double)m*b+1e-6)*m + m)%m;
}
struct matrix
{
ll A[N][N];
void init()
{
memset(A, 0, sizeof(A));
return;
}
matrix operator * (const matrix& a)const{
matrix rel;
rel.init();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
for(int k = 1; k <= n; k++)
{
rel.A[i][j] = (rel.A[i][j]+mul(A[i][k], a.A[k][j]))%m;
}
}
}
return rel;
}
matrix operator + (const matrix& a)const{
matrix rel;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
rel.A[i][j] = (A[i][j]+a.A[i][j])%m;
}
}
return rel;
}
};
int main()
{
ll k;
matrix ans, t[2][3];
freopen("matrix_sum.in","r",stdin);
freopen("matrix_sum.out","w",stdout);
scanf("%lld%lld%lld", &n, &k, &m);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%lld", &t[1][1].A[i][j]);
}
}
k--;
ans = t[1][2] = t[1][1];
while(k)
{
if(k&1)
{
ans = (t[1][2]*ans)+t[1][1];
}
t[1][1] = t[1][1]+(t[1][2]*t[1][1]);
t[1][2] = t[1][2]*t[1][2];
k >>= 1;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
printf("%lld ", ans.A[i][j]);
}
puts("");
}
return 0;
}