89
правок
Изменения
→Умножение матриц (за O(k^3 \cdot \log n))
\end{pmatrix}</tex>
Продолжая так , для любого целого неотрицательного <tex>i</tex>, мы получим столбик <tex>A_i</tex>, состоящий из <tex>k</tex> подряд идущих членов последовательности, начиная с <tex>a_i</tex>. Пользуясь ассоциативностью произведения матриц, можно записать, что <tex>A_i = T^i \cdot A_0</tex>. Из этого соотношения вытекает алгоритм вычисления произвольного <tex>a_n</tex>:
# Инициализировать матрицы <tex>A_0</tex> и <tex>T</tex>
