Matrix exponential

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
1.5 kB
4
Indexable
Never
class matrix {
public:
    vector<vector<int> >arr;
    int mod = 1e9+7;
    matrix() {}
    matrix(int N) {
        for( int i = 0 ; i < N ; i ++ ) {
            vector<int>y;
      for( int j = 0 ; j < N ; j++ ) {
                y.push_back(0);
            }
            arr.push_back(y);
        }
    }
    void changeMod(int new_mod){
      mod=new_mod;
    }
    matrix operator *(const matrix &in) {
        matrix ret ;
        int N=this->arr.size();
        ret=matrix(N);
        for( int i = 0 ; i < N ; i++ ) {
            for( int j = 0 ; j < N ; j++ )
                for( int k = 0 ; k < N ; k++ ) {
                    ret.arr[i][j]+=(arr[i][k])*(in.arr[k][j]) ;
                    ret.arr[i][j]%=mod;
                }
        }
        return ret ;
    }
    matrix operator ^( long long int POW) {
        matrix ret;
        int N=this->arr.size();
        ret=matrix(N);
        for( int i = 0 ; i < N ; i++ ) {
            ret.arr[i][i] = 1 ;
        }
        matrix ME = *this ;
        while( POW ) {
            if( POW&1 ) {
                ret = ret * ME ;
            }
            ME = ME * ME ;
            POW >>= 1 ;
        }
        return ret ;
    }
    matrix operator +(const matrix &x) {
        matrix ret;
        int N=this->arr.size();
        ret=matrix(N);
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                ret.arr[i][j]=(arr[i][j]+x.arr[i][j])%mod;
            }
        }
        return ret;
    }
};