Matrix exponential
unknown
c_cpp
4 years ago
1.5 kB
12
Indexable
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;
}
};Editor is loading...