Matrices - YessineJallouli/Competitive-Programming GitHub Wiki

// this is a structure for a square matrix 

const int mod = 1e9+7;
 
struct matrix {
    vector<vector<ll>> values;
    explicit matrix(int n) {
        values.resize(n, vector<ll>(n, 0));
    }
    static matrix identity(int n) {
        matrix res(n);
        for (int i = 0; i < n; i++)
            res.values[i][i] = 1;
        return res;
    }
    matrix operator*(const matrix& A) const {
        int n = (int) values.size();
        matrix res(n);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                for (int j = 0; j < n; j++) {
                    res.values[i][j] = (res.values[i][j] + (values[i][k]*A.values[k][j])%mod);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res.values[i][j]%= mod;
            }
        }
        return res;
    }
 
    void print() {
        int n = (int) values.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << values[i][j] << ' ';
            }
            cout << '\n';
        }
    }
};

matrix fastP(matrix &a, ll pw) {
    int n = (int) a.values.size();
    matrix ans = matrix::identity(n);
    while (pw > 0) {
        if (pw & 1)
            ans = ans*a;
        a = a*a;
        pw/=2;
    }
    return ans;
}