| ||||||||||
| 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 | |||||||||
第二种方法过不了,代码如下,怎么优化#include<iostream>
#include<cstring>
#include<cstdio>
#include<fstream>
using namespace std;
const int maxn=100;
class matrix{
public:
int size,mod;
bool flag;
int elem[maxn][maxn];
matrix(int a=0,int b=0):size(a),mod(b),flag(0){
memset(elem,0,sizeof(elem));
}
matrix operator*(const matrix&M);
matrix pow(int exp);
matrix operator+(const matrix&M);
matrix&operator=(const matrix&M);
};
matrix matrix::operator+(const matrix&M){
matrix ans(M.size,M.mod);
for(int i=0;i<M.size;i++){
for(int j=0;j<M.size;j++){
ans.elem[i][j]=elem[i][j]+M.elem[i][j];
if(ans.elem[i][j]>=M.mod)ans.elem[i][j]%=M.mod;
}
}
return ans;
}
matrix matrix::pow(int exp){
matrix tem=(*this)*(*this);
if(exp==1)return (*this);
if(exp&1){
return tem.pow(exp>>1)*(*this);
}
return tem.pow(exp>>1);
}
matrix matrix::operator*(const matrix&M){
matrix ans(M.size,M.mod);
for(int i=0;i<M.size;i++){
for(int j=0;j<M.size;j++){
for(int k=0;k<M.size;k++){
ans.elem[i][j]+=elem[i][k]*M.elem[j][k];
if(ans.elem[i][j]>=M.mod)ans.elem[i][j]%=M.mod;
}
}
}
return ans;
}
matrix&matrix::operator=(const matrix&M){
mod=M.mod;
size=M.size;
for(int i=0;i<size;i++){
for(int j=0;j<size;j++)elem[i][j]=M.elem[i][j];
}
return (*this);
}
ostream&operator<<(ostream&os,const matrix&M){
for(int i=0;i<M.size;i++){
for(int j=0;j<M.size;j++){
if(j==0)os<<M.elem[i][j];
else os<<" "<<M.elem[i][j];
}
os<<endl;
}
return os;
}
int n,m,k;
matrix A;
matrix record[10000];
matrix Pow(int exp){
if(record[exp].flag)return record[exp];
matrix tem(n,m);
if(exp==0)record[exp]= tem;
else if(exp&1){
record[exp]= Pow(exp-1)+A.pow(exp);
}
else{
tem=Pow(exp>>1);
record[exp]=tem+tem*A.pow(exp>>1);
}
record[exp].flag=1;
return record[exp];
}
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&k,&m);
A.size=n,A.mod=m;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)scanf("%d",&A.elem[i][j]);
}
matrix ans(n,m);
ans=Pow(k);
cout<<ans;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator