Fibonacci Numbers -Matrix Multiplication

The Fibonacci numbers can be defined as follows:

• F0 = 0
• F1=1
  
• Fn=Fn−2+Fn−1

Your task is to calculate the value of Fn for a given n$n$.

Example:

Input:  n = 10
Output: 55

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;
template <class T>
struct matrix
{
    vector<vector<T>> m;
    long long r, c;
    matrix() : r(), c() {}
    matrix(long long r, long long c, T x) : r(r), c(c), m(r, vector<T>(c, x)) {}
    matrix(long long n) : matrix(n, n, 0)
    {
        // identity matrix
        for (long long i = 0; i < n; i++)
            m[i][i] = 1;
    }
    matrix operator*(matrix<T> b)
    {
        matrix<T> a = *this;
        assert(a.c == b.r);
        matrix<T> o(a.r, b.c, 0);
        for (long long i = 0; i < a.r; i++)
            for (long long j = 0; j < b.c; j++)
                for (long long k = 0; k < a.c; k++)
                    o.m[i][j] = (o.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
        return o;
    }
    matrix operator^(long long b)
    {
        assert(r == c);
        matrix<T> a(r, c, 0);
        for (long long i = 0; i < r; i++)
            for (long long j = 0; j < c; j++)
                a.m[i][j] = m[i][j];
        matrix<T> o(r);
        while (b)
        {
            if (b % 2)
                o = o * a;
            a = a * a;
            b /= 2;
        }
        return o;
    }
};

long long fibonacciNumbers(long long n)
{

    matrix<long long> A(1, 2, 0);
    A.m[0][0] = 0;
    A.m[0][1] = 1;
    matrix<long long> B(2, 2, 0);
    B.m[0][0] = 0;
    B.m[0][1] = 1;
    B.m[1][0] = 1;
    B.m[1][1] = 1;
    A = A * (B ^ n);
    return A.m[0][0];
}

int main()
{
    long long n = 10;

    cout << fibonacciNumbers(n) << "\n";

    return 0;
}