#include <iostream>
using namespace std;

int LinearMethod(int n)
{
    int a = 1;
    int b = 1;
    int c = 2;
    if (n == 3)
        return c;
    if (n <= 2)
        return b;
    for (int i = 3; i < n; i++)
    {
        a = b;
        b = c;
        c = a + b;
    }
    return c;
}

int RecursiveMethod(int n)
{
    if (n <= 2)
        return 1;
    return RecursiveMethod(n - 1) + RecursiveMethod(n - 2);
}

int** MatrixMultiplication(int** matrix2, int** matrix1)
{
    int e1 = matrix1[0][0] * matrix2[0][0] + matrix1[0][1] * matrix2[1][0];
    int e2 = matrix1[0][0] * matrix2[0][1] + matrix1[0][1] * matrix2[1][1];
    int e3 = matrix1[1][0] * matrix2[0][0] + matrix1[1][1] * matrix2[1][0];
    int e4 = matrix1[1][0] * matrix2[0][1] + matrix1[1][1] * matrix2[1][1];
    return new int* [2]{ new int[2]{ e1, e2 }, new int[2]{ e3, e4 } };
}

int** BinaryExponentiation(int** matrix, int n)
{
    if (n == 0)
        return new int* [2]{ new int[2]{ 1, 0 }, new int[2]{ 0, 1 } };
    if (n % 2 == 1)
        return MatrixMultiplication(BinaryExponentiation(matrix, n - 1), matrix);
    else
    {
        int** matrixTemp = BinaryExponentiation(matrix, n / 2);
        return MatrixMultiplication(matrixTemp, matrixTemp);
    }
}

int MatrixMethod(int n)
{
    int** matrix = new int* [2]{ new int[2]{ 1, 1 }, new int[2]{ 1, 0 } };
    return BinaryExponentiation(matrix, n)[0][1];
}

int main()
{
    cout << LinearMethod(9) << endl;
    cout << RecursiveMethod(9) << endl;
    cout << MatrixMethod(9);
}