classmatrix

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long i64;

class Matrix{
private:
    vector<vector<i64>> matrix;
    i64 _base;
public:
    Matrix();
    Matrix(vector<i64>& v, i64 base = 0);
    Matrix(i64 M, i64 N, i64 val = 0, i64 base = 0);
    Matrix(Matrix& m);
    void print();
    i64 getCountRow();
    i64 getCountCol();
    i64 getBase();
    bool setVal(i64 y, i64 x, i64 val);
    i64 getVal(i64 y, i64 x);
    bool setBase(i64 base);
    bool prod(Matrix& b);
    bool prod(Matrix& a , Matrix& b);
    void power(i64 n);
    void sqr();
    void toId();
    Matrix& operator=(Matrix& m);
};

Matrix::Matrix(vector<i64>& v, i64 base){
    matrix.clear();
    _base = base;
    i64 n = round(sqrt(v.size()));
    for (i64 i = 0, k = 0; i < n; ++i){
        vector<i64> temp;
        for (i64 j = 0; j < n; ++j){
            i64 val = v[k++];
            if ( _base != 0 ) val %= _base;
            temp.push_back(val);
            if ( k >= v.size()) k %= v.size();
        }
        matrix.push_back(temp);
    }
}

void Matrix::toId(){
    i64 countR = getCountRow(), countC = getCountCol();
    for (int i = 0; i < countR; ++i)
        for (int j = 0; j < countC; ++j)
            setVal(i, j, i == j ? 1:0);
}

void Matrix::sqr(){
    Matrix temp = *this;
    prod(temp, temp);
}

void Matrix::power(i64 n){
    Matrix t = *this; t.toId();
    bool notFinished = true;
    while ( notFinished ) {
        if ( n % 2 != 0 ) t.prod(*this);
        n /= 2;
        if ( n > 0 )
            sqr();
        else
            notFinished = false;
    }
    *this = t;
}

Matrix::Matrix(){
    vector<i64> temp (1,0);
    matrix.clear();
    matrix.push_back(temp);
    _base = 0;
}

i64 Matrix::getVal(i64 y, i64 x){
    i64 countR = getCountRow(), countC = getCountCol();
    if ( y > countR ) y %= countR;
    if ( x > countC ) x %= countC;
    return matrix[y][x];
}

Matrix::Matrix(Matrix& m){
    matrix = m.matrix;
    _base = m._base;
}

Matrix& Matrix::operator=(Matrix& m){
    matrix = m.matrix;
    _base = m._base;
    return *this;
}

bool Matrix::prod(Matrix& b){
    Matrix temp = *this;
    return prod(temp, b);
}

bool Matrix::prod(Matrix& a, Matrix& b){
    i64 countRowsFromA = a.getCountRow(), countColsFromA = a.getCountCol();
    i64 countRowsFromB = b.getCountRow(), countColsFromB = b.getCountCol();

    bool flag = countColsFromA == countRowsFromB;
    if ( !flag ) return flag;
    matrix.clear();
    _base = a._base;

    for ( i64 i = 0; i < countRowsFromA; ++i ){
        vector<i64> temp;
        for ( i64 j = 0; j < countColsFromB; ++j ){
            i64 temp_val = 0;
            for (i64 k = 0; k < countColsFromA; ++k){

                temp_val += a.getVal(i, k) * b.getVal(k, j);

                if ( _base != 0 && ( temp_val >= _base || temp_val < 0 ) ) temp_val %= _base;
            }
            temp.push_back(temp_val);
        }
        matrix.push_back(temp);
    }
    return flag;
}

i64 Matrix::getCountRow(){return matrix.size();}
i64 Matrix::getCountCol(){return matrix.at(0).size();}
i64 Matrix::getBase(){return _base;}

bool Matrix::setBase(i64 base){
    bool flag = _base > base;
    _base = base;
    if (flag)
        for (auto &i : matrix) for (auto &j : i) j %= _base;
    return flag;
}

Matrix::Matrix(i64 M, i64 N, i64 val, i64 base){
    _base = base;
    if ( _base != 0 ) val %= _base;
    matrix.clear();
    for (int i=0; i<M; ++i){
        vector<i64> temp;
        for (int j = 0; j<N; ++j)
            temp.push_back(val);
        matrix.push_back(temp);
    }
}

void Matrix::print(){
    for (auto &i : matrix){
        for (auto &j : i)
            cout<<j<<" ";
        cout<<endl;
    }
}

bool Matrix::setVal(i64 y, i64 x, i64 val){
    bool flag = y < matrix.size() && x < matrix.at(0).size();
    if ( !flag ) return flag;
    if ( _base != 0 ) {
        val %= _base;
    }

    matrix[y][x] = val;
    return flag;
}

int main(){
    vector<i64> v = {0,2,1,-1};
    Matrix m(v, 5);
    Matrix n = m, k = m;
    for (int i = 0; i <=100; ++i){
        cout<<"step "<<i<<":"<<endl;
        m = n;
        m.power(i);
        m.print();
    }
    cout<<m.getBase()<<endl;

    return 0;
}