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