2021-11-09
56
Допустим нам необходимо вычислить n-ное число Фибоначчи быстрее, чем за линейное время. Представим вычисление следующего числа в виде матричного умножения:
(Fi Fi+1) * (0 1) = (Fi+1, Fi + Fi+1) = (Fi+1, Fi+2)
1 1
Обозначим матрицу, для умножения чисел Фибоначчи за P.
Заметим, что за одно умножение на матрицу P мы переходим на одно число Фибоначчи вперёд, поэтому умножив n-1 на матрицу P матрицу (F0 F1) мы получим Fn. Но умножение матриц ассоциативно поэтому мы можем просто возвести матрицу в степень, а это можно сделать за логарифмическое время.
На самом деле данную технику можно применять к любым задачам, где члены последовательности линейно зависят от предыдущих.
Пример: Задача о трёх цветках. В саду посадили R красных, G зелёных и B синих цветов. Каждую ночь все цветы вянут, а на их месте вырастают новые. На месте одного красного вырастают r1 красных, r2 зелёных, r3 синих цветов (для других цветов также известны такие закономерности). Сколько цветов каждого цвета будет через N дней, N <= 10^18.
Факт. Предел отношения чисел Фибоначчи равен золотому сечению
| const int mod = 1000000007; struct matrix { int n, m; vector<vector<ll> > v; matrix(int n, int m): n(n), m(m) { v.resize(n, vector<ll>(m, 0)); } vector<ll> & operator[] (int index) { return v[index]; } vector<ll> operator[] (int index) const { return v[index]; } matrix operator*(const matrix & b) const { matrix res(n, b.m); for (int i = 0; i < n; ++i) { for (int j = 0; j < b.m; ++j) { for (int k = 0; k < m; ++k) { res[i][j] = (res[i][j] + v[i][k] * b[k][j] % mod) % mod; } } } return res; } void print() { for (auto& i: v) { for (auto& j: i) cout << j << ' '; cout << endl; } cout << endl; } }; matrix binpow(const matrix & a, ll n) { if (n == 1) return a; if (n % 2 == 1) return a * binpow(a, n - 1); matrix b = binpow(a, n / 2); return b * b; } ... cin >> n; int n; matrix lst(1, 2), m(2, 2); lst.v = { { 0, 1 } }; m.v = { { 0, 1 }, { 1, 1 } }; if (n <= 1) { cout << lst.v[0][n]; return 0; } lst = lst * binpow(m, n - 1); cout << lst.v[0][1]; |
