Matrix exponential
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; } };