Матричное возведение в степень: Фибоначчи за O(log n), рекурренты и пути в графе

Как переписать линейную рекурренту в виде матрицы и считать n-й член за O(log n): Фибоначчи, свободный член, суммы, лестница на k шагов и число путей длины k в графе. Код на Python.

13 мин чтенияалгоритмы · математика · динамическое программирование · python

Коротко

ЧтоКак
ЗадачаНайти ana_n линейной рекурренты или число путей длины kk при n,kn, k до 101810^{18}
Главная идеяШаг рекурренты — это умножение вектора состояния на фиксированную матрицу TT. Значит, nn шагов — это TnT^n
Возведение в степеньТот же бинарный алгоритм, что и для чисел, только с умножением матриц
СложностьO(d3log⁡n)O(d^3 \log n), где dd — размер состояния (порядок рекурренты, число вершин)
Когда применятьnn огромное, а состояние маленькое: dd от 2 до нескольких десятков
  • Обычное ДП по рекурренте стоит O(n⋅d)O(n \cdot d). При n=1018n = 10^{18} это не дождаться, а log⁡21018≈60\log_2 10^{18} \approx 60 матричных умножений считаются мгновенно.
  • Вся работа — составить матрицу перехода. Возведение в степень пишется один раз.
  • Та же техника считает число путей длины kk между вершинами графа: это элемент Ak[s][t]A^k[s][t] матрицы смежности.

Откуда берётся матрица

Сам приём быстрого возведения в степень разобран в статье «Быстрое возведение в степень». Здесь он нужен как готовый инструмент. Главный вопрос в другом: как увидеть матрицу в задаче, где её нет.

Возьмём Фибоначчи: Fi+1=Fi+Fi−1F_{i+1} = F_i + F_{i-1}. Чтобы сделать шаг, нужно знать два последних значения. Соберём их в вектор состояния:

vi=(FiFi−1)v_i = \begin{pmatrix} F_i \\ F_{i-1} \end{pmatrix}

Следующее состояние выражается через текущее линейно, то есть каждая новая компонента — сумма старых с постоянными коэффициентами:

(Fi+1Fi)=(1110)(FiFi−1)\begin{pmatrix} F_{i+1} \\ F_i \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_i \\ F_{i-1} \end{pmatrix}

Первая строка матрицы говорит «новое FF равно сумме двух старых», вторая — «старое FiF_i сдвигается на место предыдущего». Обозначим матрицу через TT. Тогда vi+1=Tviv_{i+1} = T v_i, и сразу:

vn=Tn−1v1v_n = T^{n-1} v_1

Умножение матриц ассоциативно, поэтому Tn−1T^{n-1} можно считать бинарным возведением: T13=T8⋅T4⋅T1T^{13} = T^8 \cdot T^4 \cdot T^1, а T8T^8 получается тремя возведениями в квадрат. Вместо nn шагов выходит около 2log⁡2n2 \log_2 n умножений матриц 2×22 \times 2.

Это и есть весь метод. Дальше — техника составления TT для разных случаев.

Базовый код

Две функции на все примеры статьи. Умножение написано для прямоугольных матриц, чтобы им же умножать матрицу на вектор-столбец.

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

Раз v1=(1,0)Tv_1 = (1, 0)^T, произведение Tn−1v1T^{n-1} v_1 — это просто первый столбец Tn−1T^{n-1}, и умножать на вектор не нужно. В общем случае умножение на начальный вектор остаётся: начальные значения бывают любыми.

Для сравнения: цикл a, b = b, a + b на 101810^{18} итераций при скорости 10710^7 итераций в секунду работал бы около трёх тысяч лет. Матричная версия делает 60 возведений в квадрат и до 60 умножений матриц 2×22 \times 2.

Подробно про рекурсию, мемоизацию и формулу Бине для Фибоначчи — в статье «Числа Фибоначчи».

Общая рекуррента порядка k

Пусть

an=c1an−1+c2an−2+⋯+ckan−ka_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}

Состояние — последние kk значений: vi=(ai,ai−1,…,ai−k+1)Tv_i = (a_i, a_{i-1}, \dots, a_{i-k+1})^T. Матрица перехода k×kk \times k устроена всегда одинаково:

T=(c1c2⋯ck−1ck10⋯0001⋯00⋮⋱⋮00⋯10)T = \begin{pmatrix} c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix}

Первая строка считает новый член, единицы под главной диагональю сдвигают окно на одну позицию. Такую матрицу называют сопровождающей (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

Начальное состояние — vk−1=(ak−1,…,a0)v_{k-1} = (a_{k-1}, \dots, a_0), поэтому до vnv_n нужно n−k+1n - k + 1 шагов. Обратите внимание на reversed: в векторе свежие значения идут сверху. Перепутать порядок здесь — самая частая ошибка, поэтому функцию стоит сверять с наивным циклом на первых 30–50 членах. Отрицательные коэффициенты тоже работают: % в Python возвращает неотрицательный остаток.

Свободный член, n и суммы

Не каждая рекуррента однородна. Приём один: всё, что нужно для следующего шага, добавляем в вектор состояния, даже если это константа.

Константа: an=an−1+an−2+1a_n = a_{n-1} + a_{n-2} + 1

Добавим в состояние компоненту, которая всегда равна 1. Она переходит сама в себя, а в первой строке матрицы даёт «+1»:

(ai+1ai1)=(111100001)(aiai−11)\begin{pmatrix} a_{i+1} \\ a_i \\ 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} a_i \\ a_{i-1} \\ 1 \end{pmatrix}
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: an=2an−1+na_n = 2a_{n-1} + n

Номер шага тоже можно хранить в состоянии: n=(n−1)+1n = (n - 1) + 1, то есть счётчик растёт за счёт той же единицы. Состояние (ai,i,1)(a_i, i, 1):

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]

Для n2n^2 понадобятся компоненты i2,i,1i^2, i, 1: (i+1)2=i2+2i+1(i+1)^2 = i^2 + 2i + 1. Любой многочлен степени pp добавляет p+1p + 1 компоненту.

Сумма первых членов

Нужна не FnF_n, а Sn=F0+F1+⋯+FnS_n = F_0 + F_1 + \dots + F_n? Добавим накопитель в состояние: Si=Si−1+FiS_i = S_{i-1} + F_i.

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

Хороший ход на собеседовании — сначала показать ДП за O(nk)O(nk), потом окно со скользящей суммой за O(n)O(n), и только после вопроса про огромное nn — матрицу за O(k3log⁡n)O(k^3 \log n). Так видно, что вы выбираете инструмент под ограничения, а не вспоминаете заготовку.

Число путей длины k в графе

Вторая большая область применения. Пусть AA — матрица смежности ориентированного графа: A[u][v]A[u][v] — число рёбер из uu в vv.

Утверждение: Ak[s][t]A^k[s][t] равно числу путей (маршрутов, вершины могут повторяться) ровно из kk рёбер из ss в tt.

Доказательство по индукции. Для k=1k = 1 это определение AA. Пусть утверждение верно для kk. Любой путь длины k+1k + 1 из ss в tt — это путь длины kk из ss в какую-то вершину mm плюс ребро m→tm \to t. Суммируем по всем mm:

pathsk+1(s,t)=∑mpathsk(s,m)⋅A[m][t]=(Ak⋅A)[s][t]\text{paths}_{k+1}(s, t) = \sum_m \text{paths}_k(s, m) \cdot A[m][t] = (A^k \cdot A)[s][t]

Это ровно формула умножения матриц. Каждое умножение на AA — шаг ДП «где я окажусь после ещё одного ребра», а матричная степень сворачивает kk таких шагов в log⁡k\log 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]

Проверим вручную k=2k = 2: из 0 в 3 за два ребра можно только по 0→2→30 \to 2 \to 3, ответ 1. При k=3k = 3 два пути: 0→1→2→30 \to 1 \to 2 \to 3 и 0→2→3→30 \to 2 \to 3 \to 3 (по петле). Совпадает. Код также сверен с полным перебором всех последовательностей вершин для k≤6k \le 6.

Для неориентированного графа каждое ребро добавляется в обе стороны, матрица симметрична. Если нужны пути из всех вершин сразу, то AkA^k уже содержит ответы для всех пар — считать заново для каждой пары не нужно.

Пути длины не больше k

Нужна сумма A+A2+⋯+AkA + A^2 + \dots + A^k. Можно считать её рекурсией «разделяй и властвуй», но проще блочная матрица размера 2d2d:

B=(AI0I)⇒Bm=(AmI+A+⋯+Am−10I)B = \begin{pmatrix} A & I \\ 0 & I \end{pmatrix} \quad\Rightarrow\quad B^{m} = \begin{pmatrix} A^{m} & I + A + \dots + A^{m-1} \\ 0 & I \end{pmatrix}

Это тот же приём с накопителем, что и для суммы Фибоначчи, только каждая «компонента» — целая матрица.

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]

Каждое число — накопленная сумма предыдущего списка: 0,0+1,1+2,3+3,…0, 0+1, 1+2, 3+3, \dots

Другие полукольца: кратчайший путь ровно из k рёбер

Возведение в степень работает для любой ассоциативной операции. Если в умножении матриц заменить сложение на min, а умножение на +, получится «min-plus произведение»:

C[i][j]=min⁡m(A[i][m]+B[m][j])C[i][j] = \min_m \big(A[i][m] + B[m][j]\big)

Оно тоже ассоциативно, поэтому WkW^k в этом смысле даёт минимальный вес пути ровно из kk рёбер. Единичная матрица здесь — нули на диагонали и ∞\infty вне её.

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 не попасть, за два — 0→2→30 \to 2 \to 3 весом 8, дальше каждый лишний шаг стоит 1 за счёт петли у вершины 3. Если заменить операции на or и and, получится достижимость за ровно kk шагов. Это любимый «вау-момент» в олимпиадных задачах, но на обычном собеседовании до него доходят редко. Про обычные кратчайшие пути без ограничения на число рёбер — в статьях про алгоритм Дейкстры и Флойда — Уоршелла.

Сложность и пределы

ПараметрЗначение
Одно умножение матриц d×dd \times dO(d3)O(d^3)
Число умноженийне больше 2⌊log⁡2n⌋+12 \lfloor \log_2 n \rfloor + 1
ИтогоO(d3log⁡n)O(d^3 \log n) по времени, O(d2)O(d^2) по памяти

На практике в чистом Python при n=1018n = 10^{18} (около 60 возведений в квадрат и до 60 умножений) время выглядит так: d=10d = 10 — сотые доли секунды, d=50d = 50 — порядка секунды, d=100d = 100 — несколько секунд. Точные цифры зависят от машины, но порядок такой: выше d≈100d \approx 100 в Python приём становится медленным, а в C++ разумный потолок — несколько сотен.

Сравнение с обычным ДП: оно стоит O(n⋅d)O(n \cdot d) (для рекурренты) или O(n⋅d2)O(n \cdot d^2) (для путей в графе). Матрица выгодна, когда nn значительно больше d2d^2. При n=105n = 10^5 и d=50d = 50 проще и быстрее обычный цикл.

Если нужен только ana_n однородной рекурренты порядка kk, существует метод с многочленами (метод Китамасы) за O(k2log⁡n)O(k^2 \log n), а с быстрым умножением многочленов — за O(klog⁡klog⁡n)O(k \log k \log n). Он встречается в олимпиадах, на собеседованиях — практически никогда.

Типичные ошибки

  1. Порядок компонент в векторе. В матрице первая строка соответствует первой компоненте. Если вектор записан как (ai−1,ai)(a_{i-1}, a_i), коэффициенты нужно переставить. Лечится сверкой с наивным циклом на первых членах.
  2. Сдвиг на единицу в показателе. TnT^n или Tn−1T^{n-1}? Зависит от того, какой вектор стартовый. Запишите явно: «vстартv_{\text{старт}} — это состояние с индексом jj, нужно n−jn - j шагов».
  3. Переполнение в C++/Java. Произведение двух чисел меньше 109+710^9 + 7 помещается в long long, а сумма dd таких произведений уже нет. Берите остаток после каждого слагаемого или накапливайте в unsigned __int128. В Python этой проблемы нет, но без % mod числа растут экспоненциально и всё замедляется.
  4. Забытая единичная матрица. Начальный результат — II, а не TT, иначе получится Tn+1T^{n+1}. Для n=0n = 0 ответ T0=IT^0 = I должен корректно возвращать стартовое состояние.
  5. Попытка втиснуть нелинейную рекурренту. an=an−12+1a_n = a_{n-1}^2 + 1 или an=max⁡(an−1,an−2)a_n = \max(a_{n-1}, a_{n-2}) матрицей в обычном смысле не считаются. С max⁡\max иногда спасает полукольцо (max, +), но только если формула имеет вид max⁡m(am+cm)\max_m (a_m + c_m).
  6. NumPy без контроля типов. numpy.linalg.matrix_power с int64 молча переполняется, а с object теряет всю скорость. Для модульной арифметики надёжнее свой код.
  7. Путаница «путь» и «простой путь». AkA^k считает маршруты с повторениями вершин. Число простых путей длины kk — NP-трудная задача в общем случае, матрица её не решает.

Где встречается на собеседованиях

  • Follow-up к Фибоначчи и Climbing Stairs: «а если n=1018n = 10^{18}?» Самый частый сценарий. Достаточно показать состояние, матрицу и сказать, что степень считается бинарным возведением.
  • Knight Dialer (LeetCode 935) и похожие задачи «сколько последовательностей длины nn»: это пути длины n−1n - 1 в графе переходов. Обычное ДП за O(n)O(n) проходит ограничения, но вопрос «а если nn огромно» превращает задачу в матричную.
  • Count Vowels Permutation (LeetCode 1220): тот же граф переходов на 5 вершинах.
  • Олимпиадные задачи на рекурренты с модулем и пути фиксированной длины, обычно с n,kn, k до 101810^{18}.

Для подготовки полезно взять любую задачу с ДП вида dp[i] = f(dp[i-1], ..., dp[i-k]) и спросить себя: линейно ли f и маленькое ли состояние? Если да — у задачи есть матричная версия.

Что запомнить

  • Линейный шаг ДП с небольшим состоянием dd записывается как vi+1=Tviv_{i+1} = T v_i, отсюда vn=Tnv0v_n = T^{n} v_0 за O(d3log⁡n)O(d^3 \log n).
  • Сопровождающая матрица: коэффициенты в первой строке, единицы под диагональю.
  • Константы, nn, многочлены от nn и префиксные суммы добавляются как дополнительные компоненты состояния.
  • Ak[s][t]A^k[s][t] — число путей ровно из kk рёбер. Блочная матрица (AI0I)\begin{pmatrix} A & I \\ 0 & I \end{pmatrix} даёт сумму степеней.
  • Подмена операций на (min, +) даёт кратчайший путь ровно из kk рёбер.
  • Всегда сверяйте матричную версию с наивным циклом на маленьких nn.

Потренироваться в спокойной обстановке

Все задачи