Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第二种方法过不了,代码如下,怎么优化

Posted by peijian at 2012-03-17 10:03:27 on Problem 3233
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator