89
правок
Изменения
Нет описания правки
\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>
# Посчитать <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>.
Отсюда мы получаем, что многочлен <tex>R(t)</tex> имеет вид: <tex>R(t) = 1 + r_2 \cdot t^2 + r_4 \cdot t^4 + \cdots + r_{2k} \cdot t^{2k}</tex>. Однако вспомним о связи с рекуррентой, а именно мы получили, что <tex>a_n = -r_2 \cdot a_{n - 2} - r_4 \cdot a_{n - 4} - \cdots - r_{2k} \cdot a_{n - 2k}</tex>
Иными словами мы получили новое рекуррентное соотношение для данной последовательности, где каждый элемент зависит от элементов с номерами, имеющими такую же чётность, что номер исходного. То есть по сути наша последовательность разделилась на две независимых: с чётными и нечётными номерами. Можно сказать, что мы теперь ищем не <tex>a_n</tex> из исходной последовательности, а <tex>a'_{n~div~2}</tex> из подпоследовательности элементов c номерами, имеющими ту же чётность, что и <tex>n</tex>. Заметим, что этот процесс можно проделывать далее пока <tex>n \geqslant k</tex>, ведь в итоге искомый элемент окажется среди <tex>k</tex> первых. Всё, что нам нужно,{{---}} поддерживать первые <tex>k</tex> элементов для каждой новой последовательности.
Исходя из всего вышесказанного получаем алгоритм:
</code>
Вычисление <tex>a[k], a[k + 1], \cdots , a[2k - 1]</tex> занимает <tex>O(k^2)</tex> времени, ибо их всего <tex>k</tex>, а каждое каждый считается за <tex>O(k)</tex>. Умножение многочленов длины порядка <tex>k</tex> также занимает <tex>O(k^2)</tex> времени. Итераций внешнего цикла будет <tex>O(logn)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз.
Итого мы получили алгоритм, работающий за <tex>O(k^2 \cdot logn)</tex>
