Матрицы и быстрое возведение в степень

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

Возведение матрицы в степень Mⁿ бинарным методом ускоряет линейные рекурренты с O(n) до O(log n).

Зачем это в олимпиадах

Когда нужно вычислить n-й член линейной рекуррентной последовательности (Фибоначчи, трибоначчи, число способов замостить полосу) для гигантского n вроде 10¹⁸, наивный проход за O(n) бессилен. Но если переход выразить умножением вектора состояния на постоянную матрицу, то n шагов — это n-я степень матрицы, а её мы считаем бинарным возведением за O(log n). Это один из самых эффектных приёмов олимпиадной алгебры: задача, где n до 10¹⁸, решается мгновенно. Он же — основа быстрых решений ДП с линейными переходами.

Матрицы и их умножение

Матрица — прямоугольная таблица чисел. Произведение C = A·B определено, когда число столбцов A равно числу строк B: элемент C[i][j] — скалярное произведение i-й строки A на j-й столбец B. Умножение матриц не коммутативно (AB ≠ BA в общем случае), но ассоциативно — именно ассоциативность позволяет применять бинарное возведение.

def mat_mult(A, B, mod=None):
    n, m, k = len(A), len(B[0]), len(B)
    C = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            s = 0
            for t in range(k):
                s += A[i][t] * B[t][j]
            C[i][j] = s % mod if mod else s
    return C

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
print(mat_mult(A, B))      # обычное произведение

Вывод:

[[19, 22], [43, 50]]

Числа Фибоначчи через матрицу

Рекуррента Fₙ = Fₙ₋₁ + Fₙ₊₂. Запишем переход как умножение на матрицу. Если состояние — вектор (Fₙ, Fₙ₋₁), то:

(Fₙ₊₁, Fₙ) = (Fₙ + Fₙ₋₁, Fₙ) = M · (Fₙ, Fₙ₋₁), где M = [[1, 1], [1, 0]]

Применив M ровно n раз к стартовому вектору, получим n-й член. Значит Mⁿ хранит числа Фибоначчи: Mⁿ = [[Fₙ₊₁, Fₙ], [Fₙ, Fₙ₋₁]]. Остаётся возвести M в степень — бинарным методом, как числа в разделе про модулярную арифметику, только умножение теперь матричное.

def mat_mult(A, B, mod=None):
    n, m, k = len(A), len(B[0]), len(B)
    C = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            s = sum(A[i][t] * B[t][j] for t in range(k))
            C[i][j] = s % mod if mod else s
    return C

def mat_pow(M, p, mod=None):
    n = len(M)
    R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]  # единичная
    while p > 0:
        if p & 1:
            R = mat_mult(R, M, mod)
        M = mat_mult(M, M, mod)
        p >>= 1
    return R

def fib(n):
    if n == 0:
        return 0
    return mat_pow([[1, 1], [1, 0]], n)[0][1]

print([fib(i) for i in range(11)])
print(fib(50))

Вывод:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
12586269025

Первые числа Фибоначчи совпадают с эталоном, а F₅₀ = 12586269025 вычислено за ~6 матричных умножений вместо 50 сложений. Для n = 10¹⁸ разница принципиальна: O(log n) против невозможного O(n).

Фибоначчи по модулю и большие n

В задачах ответ берут по модулю. Передаём mod в матричные операции — и считаем Fₙ mod p для астрономических n. Поскольку каждое умножение берёт остаток, числа не растут.

def mat_mult(A, B, mod):
    n, m, k = len(A), len(B[0]), len(B)
    C = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            s = sum(A[i][t] * B[t][j] for t in range(k))
            C[i][j] = s % mod
    return C

def mat_pow(M, p, mod):
    n = len(M)
    R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    while p > 0:
        if p & 1:
            R = mat_mult(R, M, mod)
        M = mat_mult(M, M, mod)
        p >>= 1
    return R

MOD = 10**9 + 7
def fib_mod(n, mod):
    if n == 0:
        return 0
    return mat_pow([[1, 1], [1, 0]], n, mod)[0][1]

print(fib_mod(100, MOD))
print(fib_mod(10**18, MOD))   # огромное n — мгновенно

Вывод:

687995182
209783453

Сотый член по модулю — 687995182, а F от 10¹⁸ по модулю вычислен за миллисекунды. Тот же приём работает для любой линейной рекурренты: трибоначчи (матрица 3×3), линейных ДП-переходов, подсчёта путей в графе фиксированной длины (степень матрицы смежности).

Обобщение на любую линейную рекурренту

Если aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ, состояние — вектор из k последних членов, а матрица перехода k×k содержит коэффициенты в первой строке и сдвигающую «единичную диагональ» ниже. Возводя её в степень, получаем член за O(k³·log n). Это универсальный рецепт: распознали линейную рекурренту — построили матрицу — возвели в степень.

Разбор задачи: числа трибоначчи за O(log n)

Покажем универсальность метода на трибоначчи — Tₙ = Tₙ₋₁ + Tₙ₊₂ + Tₙ₊₃, T₀=0, T₁=T₂=1. Теперь состояние — три последних члена, а матрица перехода 3×3: первая строка — коэффициенты (1,1,1), ниже — сдвигающая диагональ. Возводим в степень — и получаем член за O(log n). Тот же шаблон работает для любой линейной рекурренты, меняется лишь размер матрицы.

def mat_mult(A, B):
    n, m, k = len(A), len(B[0]), len(B)
    return [[sum(A[i][t] * B[t][j] for t in range(k)) for j in range(m)]
            for i in range(n)]

def mat_pow(M, p):
    n = len(M)
    R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    while p > 0:
        if p & 1:
            R = mat_mult(R, M)
        M = mat_mult(M, M)
        p >>= 1
    return R

def tribonacci(n):
    if n == 0:
        return 0
    if n <= 2:
        return 1
    M = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
    # начальное состояние (T2, T1, T0) = (1, 1, 0)
    powered = mat_pow(M, n - 2)
    return powered[0][0] * 1 + powered[0][1] * 1 + powered[0][2] * 0

print([tribonacci(n) for n in range(10)])
# сверка с прямой рекуррентой
seq = [0, 1, 1]
while len(seq) < 10:
    seq.append(seq[-1] + seq[-2] + seq[-3])
print(seq)

Вывод:

[0, 1, 1, 2, 4, 7, 13, 24, 44, 81]
[0, 1, 1, 2, 4, 7, 13, 24, 44, 81]

Матричная версия совпала с прямой рекуррентой: 0,1,1,2,4,7,13,…. Заметьте, что от Фибоначчи нас отделило лишь увеличение матрицы до 3×3 и подгонка стартового вектора — структура алгоритма та же. Это и есть рецепт: k членов рекурренты ⟶ матрица k×k ⟶ возведение в степень за O(k³·log n).

Подводные камни

Умножение не коммутативно. Порядок множителей важен; единичная матрица — нейтральный элемент.
Берите модуль внутри умножения. Иначе в C++ переполнение; в Python — рост чисел и замедление.
Правильный стартовый вектор. Сверьте маленькие n с эталоном — легко ошибиться на единицу в индексах.
Сложность. O(k³·log n): для больших k матрица дорогая, но при малом k (2−6) — мгновенно.

Итог

Линейный переход = умножение вектора состояния на постоянную матрицу M.
Mⁿ бинарным возведением — O(log n) вместо O(n).
Для Фибоначчи M = [[1,1],[1,0]], и Fₙ = (Mⁿ)[0][1].
Метод обобщается на любую линейную рекурренту матрицей k×k за O(k³·log n).