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