89
правок
Изменения
Нет описания правки
# Возвести матрицу <tex>T</tex> в степень <tex>n</tex>
# Посчитать <tex>A_n</tex> как <tex>T^n \cdot A_0</tex> и взять из него <tex>a_n</tex>
Используя быстрое возведения в степень второй пункт будет тратить <tex>O(k^3 \cdot logn)</tex> времени, умножение же в третьем пункте выполняется за <tex>O(k^2)</tex>. Итого мы получили алгоритм за <tex>O(k^3 \cdot logn)</tex>.
