Матричное возведение в степень: Фибоначчи за O(log n), рекурренты и пути в графе
Как переписать линейную рекурренту в виде матрицы и считать n-й член за O(log n): Фибоначчи, свободный член, суммы, лестница на k шагов и число путей длины k в графе. Код на Python.
Коротко
| Что | Как |
|---|---|
| Задача | Найти линейной рекурренты или число путей длины при до |
| Главная идея | Шаг рекурренты — это умножение вектора состояния на фиксированную матрицу . Значит, шагов — это |
| Возведение в степень | Тот же бинарный алгоритм, что и для чисел, только с умножением матриц |
| Сложность | , где — размер состояния (порядок рекурренты, число вершин) |
| Когда применять | огромное, а состояние маленькое: от 2 до нескольких десятков |
- Обычное ДП по рекурренте стоит . При это не дождаться, а матричных умножений считаются мгновенно.
- Вся работа — составить матрицу перехода. Возведение в степень пишется один раз.
- Та же техника считает число путей длины между вершинами графа: это элемент матрицы смежности.
Откуда берётся матрица
Сам приём быстрого возведения в степень разобран в статье «Быстрое возведение в степень». Здесь он нужен как готовый инструмент. Главный вопрос в другом: как увидеть матрицу в задаче, где её нет.
Возьмём Фибоначчи: . Чтобы сделать шаг, нужно знать два последних значения. Соберём их в вектор состояния:
Следующее состояние выражается через текущее линейно, то есть каждая новая компонента — сумма старых с постоянными коэффициентами:
Первая строка матрицы говорит «новое равно сумме двух старых», вторая — «старое сдвигается на место предыдущего». Обозначим матрицу через . Тогда , и сразу:
Умножение матриц ассоциативно, поэтому можно считать бинарным возведением: , а получается тремя возведениями в квадрат. Вместо шагов выходит около умножений матриц .
Это и есть весь метод. Дальше — техника составления для разных случаев.
Базовый код
Две функции на все примеры статьи. Умножение написано для прямоугольных матриц, чтобы им же умножать матрицу на вектор-столбец.
MOD = 10**9 + 7 def mat_mul(a, b, mod=MOD): n, m, p = len(a), len(b), len(b[0]) res = [[0] * p for _ in range(n)] for i in range(n): row = res[i] for k in range(m): aik = a[i][k] if aik == 0: continue bk = b[k] for j in range(p): row[j] += aik * bk[j] for j in range(p): row[j] %= mod return res def identity(n): return [[int(i == j) for j in range(n)] for i in range(n)] def mat_pow(m, e, mod=MOD): res = identity(len(m)) while e > 0: if e & 1: res = mat_mul(res, m, mod) m = mat_mul(m, m, mod) e >>= 1 return res
Пара деталей, которые экономят время в Python:
- порядок циклов
i, k, jвместоi, j, k: внутренний цикл бежит по строкеb[k], иa[i][k]достаётся один раз; % modберётся один раз на элемент результата, а не на каждое слагаемое. В Python целые числа не переполняются, а в C++ или Java так делать нельзя (см. «Типичные ошибки»);- нулевые элементы пропускаются: матрицы переходов часто разреженные.
Фибоначчи за O(log n)
def fib(n, mod=MOD): if n == 0: return 0 # v_n = T^(n-1) * v_1, v_1 = (F_1, F_0) = (1, 0) return mat_pow([[1, 1], [1, 0]], n - 1, mod)[0][0] print(fib(10)) # 55 print(fib(100)) # 687995182 (F_100 по модулю 10^9 + 7) print(fib(10**18)) # 209783453
Раз , произведение — это просто первый столбец , и умножать на вектор не нужно. В общем случае умножение на начальный вектор остаётся: начальные значения бывают любыми.
Для сравнения: цикл a, b = b, a + b на итераций при скорости итераций в секунду работал бы около трёх тысяч лет. Матричная версия делает 60 возведений в квадрат и до 60 умножений матриц .
Подробно про рекурсию, мемоизацию и формулу Бине для Фибоначчи — в статье «Числа Фибоначчи».
Общая рекуррента порядка k
Пусть
Состояние — последние значений: . Матрица перехода устроена всегда одинаково:
Первая строка считает новый член, единицы под главной диагональю сдвигают окно на одну позицию. Такую матрицу называют сопровождающей (companion matrix).
def linear_rec(coefs, init, n, mod=MOD): """a_n = coefs[0]*a_{n-1} + ... + coefs[k-1]*a_{n-k}; init = [a_0, ..., a_{k-1}]""" k = len(coefs) if n < k: return init[n] % mod T = [coefs[:]] + [[int(j == i) for j in range(k)] for i in range(k - 1)] P = mat_pow(T, n - k + 1, mod) state = [[x] for x in reversed(init)] # (a_{k-1}, ..., a_0) return mat_mul(P, state, mod)[0][0] # трибоначчи: a_n = a_{n-1} + a_{n-2} + a_{n-3}, a_0 = a_1 = 0, a_2 = 1 print([linear_rec([1, 1, 1], [0, 0, 1], n) for n in range(10)]) # [0, 0, 1, 1, 2, 4, 7, 13, 24, 44] print(linear_rec([1, 1, 1], [0, 0, 1], 10**18)) # 913728402
Начальное состояние — , поэтому до нужно шагов. Обратите внимание на reversed: в векторе свежие значения идут сверху. Перепутать порядок здесь — самая частая ошибка, поэтому функцию стоит сверять с наивным циклом на первых 30–50 членах. Отрицательные коэффициенты тоже работают: % в Python возвращает неотрицательный остаток.
Свободный член, n и суммы
Не каждая рекуррента однородна. Приём один: всё, что нужно для следующего шага, добавляем в вектор состояния, даже если это константа.
Константа:
Добавим в состояние компоненту, которая всегда равна 1. Она переходит сама в себя, а в первой строке матрицы даёт «+1»:
def rec_const(n, mod=MOD): # a_n = a_{n-1} + a_{n-2} + 1, a_0 = 0, a_1 = 1 if n < 2: return n T = [[1, 1, 1], [1, 0, 0], [0, 0, 1]] state = [[1], [0], [1]] # (a_1, a_0, 1) return mat_mul(mat_pow(T, n - 1, mod), state, mod)[0][0] print([rec_const(n) for n in range(10)]) # [0, 1, 2, 4, 7, 12, 20, 33, 54, 88]
Слагаемое n:
Номер шага тоже можно хранить в состоянии: , то есть счётчик растёт за счёт той же единицы. Состояние :
def rec_poly(n, mod=MOD): # a_n = 2*a_{n-1} + n, a_0 = 1 T = [[2, 1, 1], # a_{i+1} = 2*a_i + i + 1 [0, 1, 1], # i + 1 = i + 1 [0, 0, 1]] # 1 = 1 state = [[1], [0], [1]] # (a_0, 0, 1) return mat_mul(mat_pow(T, n, mod), state, mod)[0][0] print([rec_poly(n) for n in range(8)]) # [1, 3, 8, 19, 42, 89, 184, 375]
Для понадобятся компоненты : . Любой многочлен степени добавляет компоненту.
Сумма первых членов
Нужна не , а ? Добавим накопитель в состояние: .
def fib_sum(n, mod=MOD):
# состояние (F_{i+1}, F_i, S_{i-1}), где S_i = F_0 + ... + F_i
T = [[1, 1, 0], # F_{i+2} = F_{i+1} + F_i
[1, 0, 0], # F_{i+1}
[0, 1, 1]] # S_i = S_{i-1} + F_i
state = [[1], [0], [0]] # i = 0: (F_1, F_0, S_{-1} = 0)
return mat_mul(mat_pow(T, n + 1, mod), state, mod)[2][0]
print([fib_sum(n) for n in range(10)]) # [0, 1, 2, 4, 7, 12, 20, 33, 54, 88]
Вывод совпал с `rec_const` не случайно: $S_n = F_{n+2} - 1$, и эта сумма удовлетворяет той же рекурренте $S_n = S_{n-1} + S_{n-2} + 1$. Хорошая самопроверка: два разных построения дали одинаковые числа.
Правило для составления матрицы: **выпишите, что нужно знать для следующего шага, и проверьте, что каждая новая компонента — линейная комбинация старых**. Если в формуле есть $a_{i}^2$, $\max$ или деление на $a_i$, рекуррента нелинейна, и матрица не построится.
## Лестница с шагами от 1 до k
Классическая задача [«Подъём по лестнице»](/blog/climbing-stairs): сколькими способами подняться на $n$ ступенек шагами по 1 или 2. Ответ — числа Фибоначчи, а на собеседовании её решают ДП за $O(n)$. Типичный follow-up: «а если шагать можно на 1, 2, …, k ступенек, и $n$ до $10^{18}$?»
$$
\text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2) + \dots + \text{ways}(n-k), \quad \text{ways}(0) = 1
$$
Это рекуррента порядка $k$ со всеми коэффициентами 1. Удобно считать, что $\text{ways}$ от отрицательных аргументов равен 0, тогда стартовое состояние — $(1, 0, \dots, 0)$, и не нужно отдельно разбирать маленькие $n$:
```python
def stairs(n, k, mod=MOD):
T = [[1] * k] + [[int(j == i) for j in range(k)] for i in range(k - 1)]
state = [[1]] + [[0]] * (k - 1) # (ways(0), ways(-1), ..., ways(-k+1))
return mat_mul(mat_pow(T, n, mod), state, mod)[0][0]
print(stairs(5, 2)) # 8
print(stairs(5, 3)) # 13
print(stairs(10**18, 3)) # 538436942
Хороший ход на собеседовании — сначала показать ДП за , потом окно со скользящей суммой за , и только после вопроса про огромное — матрицу за . Так видно, что вы выбираете инструмент под ограничения, а не вспоминаете заготовку.
Число путей длины k в графе
Вторая большая область применения. Пусть — матрица смежности ориентированного графа: — число рёбер из в .
Утверждение: равно числу путей (маршрутов, вершины могут повторяться) ровно из рёбер из в .
Доказательство по индукции. Для это определение . Пусть утверждение верно для . Любой путь длины из в — это путь длины из в какую-то вершину плюс ребро . Суммируем по всем :
Это ровно формула умножения матриц. Каждое умножение на — шаг ДП «где я окажусь после ещё одного ребра», а матричная степень сворачивает таких шагов в умножений.
# рёбра: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3 (петля) edges = [(0, 1), (0, 2), (1, 2), (2, 0), (2, 3), (3, 3)] n = 4 A = [[0] * n for _ in range(n)] for u, v in edges: A[u][v] += 1 # += , а не = : кратные рёбра считаются отдельно def count_walks(A, k, s, t, mod=MOD): return mat_pow(A, k, mod)[s][t] print([count_walks(A, k, 0, 3) for k in range(1, 8)]) # [0, 1, 2, 3, 5, 7, 10]
Проверим вручную : из 0 в 3 за два ребра можно только по , ответ 1. При два пути: и (по петле). Совпадает. Код также сверен с полным перебором всех последовательностей вершин для .
Для неориентированного графа каждое ребро добавляется в обе стороны, матрица симметрична. Если нужны пути из всех вершин сразу, то уже содержит ответы для всех пар — считать заново для каждой пары не нужно.
Пути длины не больше k
Нужна сумма . Можно считать её рекурсией «разделяй и властвуй», но проще блочная матрица размера :
Это тот же приём с накопителем, что и для суммы Фибоначчи, только каждая «компонента» — целая матрица.
def count_walks_upto(A, k, s, t, mod=MOD): n = len(A) B = [[0] * (2 * n) for _ in range(2 * n)] for i in range(n): for j in range(n): B[i][j] = A[i][j] B[i][n + i] = 1 B[n + i][n + i] = 1 P = mat_pow(B, k + 1, mod) # правый верхний блок B^(k+1) = I + A + ... + A^k; вычитаем I (пути длины 0) return (P[s][n + t] - (s == t)) % mod print([count_walks_upto(A, k, 0, 3) for k in range(1, 8)]) # [0, 1, 3, 6, 11, 18, 28]
Каждое число — накопленная сумма предыдущего списка:
Другие полукольца: кратчайший путь ровно из k рёбер
Возведение в степень работает для любой ассоциативной операции. Если в умножении матриц заменить сложение на min, а умножение на +, получится «min-plus произведение»:
Оно тоже ассоциативно, поэтому в этом смысле даёт минимальный вес пути ровно из рёбер. Единичная матрица здесь — нули на диагонали и вне её.
INF = float('inf') def minplus_mul(a, b): n = len(a) res = [[INF] * n for _ in range(n)] for i in range(n): for k in range(n): if a[i][k] == INF: continue for j in range(n): if a[i][k] + b[k][j] < res[i][j]: res[i][j] = a[i][k] + b[k][j] return res def minplus_pow(W, e): n = len(W) res = [[0 if i == j else INF for j in range(n)] for i in range(n)] while e > 0: if e & 1: res = minplus_mul(res, W) W = minplus_mul(W, W) e >>= 1 return res W = [[INF, 4, 1, INF], [INF, INF, 2, INF], [3, INF, INF, 7], [INF, INF, INF, 1]] print([minplus_pow(W, k)[0][3] for k in range(1, 7)]) # [inf, 8, 9, 10, 11, 12]
Ровно за одно ребро из 0 в 3 не попасть, за два — весом 8, дальше каждый лишний шаг стоит 1 за счёт петли у вершины 3. Если заменить операции на or и and, получится достижимость за ровно шагов. Это любимый «вау-момент» в олимпиадных задачах, но на обычном собеседовании до него доходят редко. Про обычные кратчайшие пути без ограничения на число рёбер — в статьях про алгоритм Дейкстры и Флойда — Уоршелла.
Сложность и пределы
| Параметр | Значение |
|---|---|
| Одно умножение матриц | |
| Число умножений | не больше |
| Итого | по времени, по памяти |
На практике в чистом Python при (около 60 возведений в квадрат и до 60 умножений) время выглядит так: — сотые доли секунды, — порядка секунды, — несколько секунд. Точные цифры зависят от машины, но порядок такой: выше в Python приём становится медленным, а в C++ разумный потолок — несколько сотен.
Сравнение с обычным ДП: оно стоит (для рекурренты) или (для путей в графе). Матрица выгодна, когда значительно больше . При и проще и быстрее обычный цикл.
Если нужен только однородной рекурренты порядка , существует метод с многочленами (метод Китамасы) за , а с быстрым умножением многочленов — за . Он встречается в олимпиадах, на собеседованиях — практически никогда.
Типичные ошибки
- Порядок компонент в векторе. В матрице первая строка соответствует первой компоненте. Если вектор записан как , коэффициенты нужно переставить. Лечится сверкой с наивным циклом на первых членах.
- Сдвиг на единицу в показателе. или ? Зависит от того, какой вектор стартовый. Запишите явно: « — это состояние с индексом , нужно шагов».
- Переполнение в C++/Java. Произведение двух чисел меньше помещается в
long long, а сумма таких произведений уже нет. Берите остаток после каждого слагаемого или накапливайте вunsigned __int128. В Python этой проблемы нет, но без% modчисла растут экспоненциально и всё замедляется. - Забытая единичная матрица. Начальный результат — , а не , иначе получится . Для ответ должен корректно возвращать стартовое состояние.
- Попытка втиснуть нелинейную рекурренту. или матрицей в обычном смысле не считаются. С иногда спасает полукольцо (max, +), но только если формула имеет вид .
- NumPy без контроля типов.
numpy.linalg.matrix_powerсint64молча переполняется, а сobjectтеряет всю скорость. Для модульной арифметики надёжнее свой код. - Путаница «путь» и «простой путь». считает маршруты с повторениями вершин. Число простых путей длины — NP-трудная задача в общем случае, матрица её не решает.
Где встречается на собеседованиях
- Follow-up к Фибоначчи и Climbing Stairs: «а если ?» Самый частый сценарий. Достаточно показать состояние, матрицу и сказать, что степень считается бинарным возведением.
- Knight Dialer (LeetCode 935) и похожие задачи «сколько последовательностей длины »: это пути длины в графе переходов. Обычное ДП за проходит ограничения, но вопрос «а если огромно» превращает задачу в матричную.
- Count Vowels Permutation (LeetCode 1220): тот же граф переходов на 5 вершинах.
- Олимпиадные задачи на рекурренты с модулем и пути фиксированной длины, обычно с до .
Для подготовки полезно взять любую задачу с ДП вида dp[i] = f(dp[i-1], ..., dp[i-k]) и спросить себя: линейно ли f и маленькое ли состояние? Если да — у задачи есть матричная версия.
Что запомнить
- Линейный шаг ДП с небольшим состоянием записывается как , отсюда за .
- Сопровождающая матрица: коэффициенты в первой строке, единицы под диагональю.
- Константы, , многочлены от и префиксные суммы добавляются как дополнительные компоненты состояния.
- — число путей ровно из рёбер. Блочная матрица даёт сумму степеней.
- Подмена операций на (min, +) даёт кратчайший путь ровно из рёбер.
- Всегда сверяйте матричную версию с наивным циклом на маленьких .