Введение

Пусть нам дана следующая задача:

Вам необходимо найти $$$n$$$ — ное число Фибоначчи ($$$n$$$ — натуральное число, $$$n \leq 10^6$$$). Последовательность Фибоначчи задается следующим образом:

• $$$F_1 = 1$$$
• $$$F_2 = 1$$$
• $$$F_i = F_{i - 1} + F_{i - 2}$$$ $$$^{*1}$$$

Поскольку $$$n$$$ — ное число может быть очень большим, то выведите его по модулю $$$10^9 + 7$$$.

Сразу после прочтения данной задачи, всем в голову приходит очевидное решение задачи.

Очевидное решение задачи

Мы будем хранить массив $$$fib$$$, в котором будут наши числа Фибоначчи, а их индексы будут обозначать какими по порядку идут эти числа. Мы запишем для удобства первые два числа из последовательности в наш массив ($$$fib[1] = 1, fib[2] = 1$$$).

Далее, мы, начиная с 3 — его элемента, будем вычислять $$$i$$$ — ое число Фибоначчи как сумму двух предыдущих (см. пункт $$$^{*1}$$$ ). То есть $$$fib[i] = fib[i - 1] + fib[i - 2]$$$ (надо не забывать, что еще нужно смотреть вычисление по модулю, поэтому $$$fib[i] = (fib[i - 1] + fib[i - 2])$$$ $$$\%$$$ $$$mod$$$, где $$$mod = 10^9 + 7$$$ по условию). Будем мы делать такие вычисления до тех пор, пока не дойдем до $$$n$$$ — ного числа. И далее мы просто выведем $$$fib[n]$$$.

#include <bits/stdc++.h>

using namespace std;

const int Size = 1e6 + 1;
int fib[Size];

int main() {
    
    int n; cin >> n;
    int mod = 1e9 + 7;
    
    fib[1] = 1;
    fib[2] = 1;
    
    for (int x = 3; x <= n; ++x) {
        fib[x] = (fib[x - 1] + fib[x - 2]) % mod;
    }
    
    cout << fib[n];
    
    return 0;
}

Нетрудно оценить время работы — оно будет $$$O(n)$$$, поскольку для каждого числа до $$$n$$$ мы вычисляем за $$$O(1)$$$ его значение. И казалось бы, мы решили задачу, но представим другую ситуацию. Пусть $$$n$$$ имеет значение до $$$10^9$$$, и ограничение по времени на задачу $$$1$$$ секунда, а по памяти такое, что не позволит хранить массив. Мы можем решать такую задачу и без массива, но и это сильно не повлияет на асимптотику кода по времени в $$$O(n)$$$, которое не сможет выполниться за $$$1$$$ секунду. Нам нужно более оптимальное решение, о котором я расскажу далее. Но чтобы его осознать, нам нужно познакомиться с поверхностной теорией о матрицах.

Немного о матрицах

Я буду использовать следующую небольшую терминологию.

Давайте научимся делать следующие три алгебраические операции: сложение, вычитание и умножение. Начнем со сложения и вычитания.

Сложение и вычитание матриц

Складывать и вычитать 2 матрицы мы можем только в том случае, когда они имеют одинаковый размер, то есть одинаковое количество строк и столбцов. Например, следующие две матрицы мы можем сложить:

А если бы у какой-то из этих матриц отличалось количество строк или столбцов, то мы не смогли бы сложить.

Суммой матриц $$$A$$$ и $$$B$$$ с размерами $$$n$$$ x $$$m$$$ называется матрица $$$C$$$ с размером $$$n$$$ x $$$m$$$, все элементы которой равны попарной сумме всех соответствующих элементов матриц $$$A$$$ и $$$B$$$, то есть каждый элемент матрицы $$$C$$$ равен: $$$c_{ij} = a_{ij} + b_{ij}$$$, где $$$i$$$ обозначает строку, а $$$j$$$ — столбец ($$$1 \leq i \leq n, 1 \le j \leq m$$$).

Так как любое вычитание можно заменить сложением (напр. $$$7 - 5 = 7 + (-5)$$$), то вычитание матриц $$$A$$$ и $$$B$$$ можно также заменить суммой матрицы $$$A$$$ и противоположной матрицы $$$B$$$, то есть $$$A - B = A + (-B)$$$.

Пример суммы матриц:

Пример разности матриц:

Также существуют некоторые свойства сложения матриц.

Умножение матриц

Умножать матрицу $$$A$$$ на $$$B$$$ можно только в том случае, если количество столбцов матрицы $$$A$$$ совпадает с количеством строк матрицы $$$B$$$. Например, следующие две матрицы можно умножить:

Умножение матриц (обозначается как $$$AB$$$, реже — $$$A$$$ x $$$B$$$) — это операция вычисления матрицы $$$C$$$, каждый элемент которой равен сумме произведений элементов в соответствующей строке первого множителя и столбце второго, или по-другому:

$$$c_{ij} = \sum\limits_{k = 1}^n a_{ik} + b_{kj}$$$

Если матрица $$$A$$$ имеет размеры $$$n$$$ x $$$m$$$, а матрица $$$B$$$ — $$$m$$$ x $$$k$$$, то матрица $$$C$$$ будет иметь размер $$$n$$$ x $$$k$$$.

И для умножения матриц существует свои свойства.

Пример умножения матриц (на основе предыдущей картинки):

Теперь, когда мы познакомились с небольшой теорией о матрицах, мы можем приступить к оптимальному решению нашей задачи.

Оптимальное решение задачи

Давайте будем представлять два подряд идущих элемента последовательности Фибоначчи как вектор-строку с размерам $$$1$$$ x $$$2$$$, то есть:

Нам нужно научиться умножать нашу вектор-строку на какую-то матрицу $$$A$$$, чтобы мы смогли получить следующую вектор-строку, то есть:

Так как количество строк первой матрицы такое же, как и у итоговой матрицы, то это означает, что мы можем подобрать некоторую матрицу $$$A$$$.

Поскольку мы знаем размеры первого множителя и того, что получилось в результате умножения, то мы сможем узнать размеры матрицы $$$A$$$ — это будет $$$2$$$ x $$$2$$$ (Поскольку количество строк у матрицы $$$A$$$ должно совпадать с количеством столбцов первой матрицы, а количество столбцов итоговой матрицы должно совпадать с количеством столбцов матрицы $$$A$$$). То есть матрица $$$A$$$ имеет вид:

Давайте найдем произведение первой вектор-строки и матрицы $$$A$$$:

Нам надо, чтобы выполнилось следующее равенство:

А так как мы знаем, что $$$F_{i + 2} = F_{i + 1} + F_{i}$$$, то $$$a_2 = 1$$$, $$$a_4 = 1$$$. И поскольку очевидно, что $$$F_{i + 1} = F_{i + 1}$$$, то $$$a_1 = 0$$$, $$$a_3 = 1$$$. Получается, что матрица $$$A$$$ будет иметь вид:

Мы нашли такую матрицу $$$A$$$, что умножив на нее матрицу из двух чисел Фибоначчи с индексами $$$i$$$, $$$i + 1$$$, мы получаем новую матрицу из двух чисел Фибоначчи с индексами $$$i + 1$$$, $$$i + 2$$$. Поэтому следующее выражение будет верно:

Наше решение будет заключаться в том, что мы вектор-строку с числами Фибоначчи с индексами $$$0$$$ и $$$1$$$ ($$$F_0 = 0$$$, $$$F_1 = 1$$$) будем умножать на матрицу $$$A$$$ в степени $$$n$$$, а затем из итоговой вектор-строки выведем первое число (то есть число, стоящее на пересечении $$$1$$$ — ой строки и $$$1$$$ — ого столбца).

И как многие уже догадались, мы будем возводить матрицу $$$A$$$ в степень $$$n$$$ при помощи быстрого возведения в степень. Для матрицы $$$A$$$ она будет выглядеть так:

В данном случае, $$$\frac{n}{2}$$$ обозначает деление $$$n$$$ на $$$2$$$ с округлением вниз, а $$$n$$$ % $$$2$$$ — остаток при делении на $$$2$$$. Больше информации про быстрое возведение в степень можно найти в интернете.

Все! Мы научились решать данную задачу, осталось ее реализовать.

#include <bits/stdc++.h>

using namespace std;

struct fib { long long fib1, fib2; }; /* используем структуру, чтобы хранить вектор - строку
                                      fib1 - число из 1-ой строки, 1-ого столбца
                                      fib2 - число из 1-ой строки, 2-ого столбца
                                      */
struct A { long long a1, a2, a3, a4; };// также используем структуру, чтобы хранить матрицу A
                                      
fib st; A st1; // создадим начальные вектор-строку и матрицу A


// нужно не забывать смотреть числа по модулю, поэтому создадим отдельную функцию для этого
const long long md = (1e9 + 7);
long long mod(long long a) { 
    return a % md;
}

// функция произведения двух матриц размерами 2x2, необходимо для вычисления A в степени N
A comp(A a, A b) {
    long long b1 = mod(a.a1 * b.a1 + a.a2 * b.a3);
    long long b2 = mod(a.a1 * b.a2 + a.a2 * b.a4);
    long long b3 = mod(a.a3 * b.a1 + a.a4 * b.a3);
    long long b4 = mod(a.a3 * b.a2 + a.a4 * b.a4);

    return { b1, b2, b3, b4 };
}

// функция произведения вектор строки 1x2 и матрицы 2x2, пригодится для итогового ответа
fib comp1(A a, fib b) {
    long long b1 = mod(b.fib1 * a.a1 + b.fib2 * a.a3);
    long long b2 = mod(b.fib1 * a.a2 + b.fib2 * a.a4);

    return { b1, b2 };
}

// функция для возведения A в степень n
A step(A a, long long n) {
    if (n == 0) return { 1, 0, 0, 1 };
    if (n == 1) return { 0, 1, 1, 1 };

    A f = step(a, n / 2);

    return comp(f, comp(f, step(a, n % 2))); // смотрите предыдущую картинку для ясного понимания того, что здесь происходит
}

int main()
{

    long long n;
    cin >> n; 

    // задаем элементы начальных матриц
    st.fib1 = 0, st.fib2 = 1;
    st1.a1 = 0, st1.a2 = 1, st1.a3 = 1, st1.a4 = 1;

    // возводим A в степень
    st1 = step(st1, n);
    // смотрим произведение начальной вектор-строки и матрицы A в степени N
    st = comp1(st1, st);

    // выводим ответ
    cout << st.fib1;
}

Асимптотика по времени данного кода будет составлять $$$O(log_2 n)$$$, поскольку мы вычисляем $$$F_n$$$ — ное число Фибоначчи при помощи быстрого возведения в степень, асимптотика которого как раз составляет $$$O(log_2 n)$$$. И поэтому время выполнения кода будет гораздо быстрее, чем $$$1$$$ секунда.