| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
代码+注释 //1688K 797MS G++//848K 829MS C++//#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 30;
int n,m,k;
typedef struct matrix
{
int a[maxn][maxn],r;
matrix(int rr):r(rr)
{
for(int i=0;i<r;++i)//初始化成e矩阵
for(int j=0;j<r;++j)
if(i==j) a[i][i]=1;
else a[i][j]=0;
}
void m0()//变成0矩阵
{
for(int i=0;i<r;++i)
for(int j=0;j<r;++j)
a[i][j] = 0;
}
}mat;
mat e(30);//identity matrix
mat operator *(const mat & a,const mat &b)//重载*运算符
{
mat c(n);
c.m0();
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(a.a[i][j])
for(int l=0;l<n;++l)
c.a[i][l] = (c.a[i][l]+a.a[i][j]*b.a[j][l])%m;
return c;
}
mat operator +(const mat & a,const mat &b)//重载+运算符
{
mat c(n);
c.m0();
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
c.a[i][j] = (a.a[i][j]+b.a[i][j])%m;
return c;
}
mat Pow(mat a,int t)//矩阵快速幂
{
mat res(n);//res存储结果,初始化为e矩阵
while(t)
{
if(t & 1) res = a*res;
a = a*a;
t>>=1;
}
return res;
}
mat solve(mat a,int k)//等比数列二分求和
{
if(k==1)
return a;
if(k & 1)
return solve(a,k-1)+Pow(a,k);//当n是奇数,f[n]=f[n-1]+A^(n);
else
return solve(a,k>>1)*(Pow(a,k>>1)+e);//当n是偶数,f[n]=f[n/2]*(A^(n/2)+E);
}
int main()
{
while(scanf("%d%d%d",&n,&k,&m)!=EOF)
{
mat a(n);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%d",&a.a[i][j]);
mat ans(n);
ans = solve(a,k);
//输出答案
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
printf("%d%c",ans.a[i][j],((j==n-1)?'\n':' '));
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator