---
# System prepended metadata

title: 12767 - The One Function and The Power Of Matrix
tags: [class]

---

# 12767 - The One Function and The Power Of Matrix
>author: Utin
###### tags: `class`
---

## Brief
See the code below

## Solution 0

```cpp=
#include <bits/stdc++.h>
#include "function.h"

// TODO: The Destructor
Matrix::~Matrix() {
    for (int i = 0; i < n; i++) delete[] matrix[i];
    delete[] matrix;
}

// TODO: The Customize Constructor
Matrix::Matrix(int n) {
    this->n = n;
    this->matrix = new long long* [n];
    for (int i = 0; i < n; i++) {
        this->matrix[i] = new long long[n];
    }
    toZero();
}

// TODO: Copy contructor
// Will be trigger when the following condition:
// Matrix m = ref; -> Call copy contructor to copy from 'ref' to 'm'
Matrix::Matrix(const Matrix& ref) {
    this->n = ref.n;
    this->matrix = new long long* [n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new long long[n];
        for (int j = 0; j < n; j++) {
            this->matrix[i][j] = ref.matrix[i][j];
        }
    }
}

// TODO: copy assignment,
// Will be trigger when the following condition:
// Matrix a;
// a = ref; -> Call copy assignment to copy from 'ref' to 'a'
Matrix& Matrix::operator=(const Matrix& ref) {
    this->n = ref.n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            this->matrix[i][j] = ref.matrix[i][j];
        }
    }
    return *this;
}

// TODO: Overload operator()
// This operator allow the following code
// This operator can help you access the data easily
// 1. cout << m(1, 2) << endl; -> Shorthand of `cout << m.matrix[1, 2] << endl;`
// 2. m(1, 2) = 100; -> Shorthand of `m.matrix[1, 2] = 100`
long long& Matrix::operator()(const int& row, const int& column) const {
    return this->matrix[row][column];
}

// Utilities functions
// TODO: Make the matrix identity matrix
void Matrix::toIdentity() {
    for (int i = 1; i < this->n; i++) {
        this->matrix[i - 1][i] = 1;
    }
    for (int i = 0; i < this->n; i++) {
        this->matrix[this->n - 1][i] = 1;
    }
}

// TODO: Overload operator * 
Matrix Matrix::operator*(const Matrix& rhs) const {
    Matrix new_matrix(n);
    // matrix multiple
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            for (int k = 0; k < n; k++) {
                long long a = this->matrix[r][k], b = rhs.matrix[k][c];
                new_matrix.matrix[r][c] = (new_matrix.matrix[r][c] + a * b) % mod;
            }
        }
    }

    return new_matrix;
}

// TODO: Return the matrix power of 'k'
Matrix Matrix::power(int k) const {
    Matrix tmp(*this);
    // tmp = *this;
    if (k == 1) return tmp;
    else if (k % 2) {
        tmp = power(k / 2);
        return tmp * tmp * (*this);
    }
    else {
        tmp = power(k / 2);
        return tmp * tmp;
    }
}

// TODO: Construct a matrix
Matrix constructMatrix(int n) {
    Matrix new_matrix(n);
    new_matrix.toIdentity();
    return new_matrix;
}

// Utin
```

## Reference