89
правок
Изменения
Нет описания правки
== Умножение матриц (за <tex>O(k^3 \cdot \log n)</tex>) ==
Заметим, что линейные рекурренты ЛРП хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик.
<tex>A_0 = \begin{pmatrix}
a_{k - 1}\\
== Связь с многочленами (за <tex>O(k^2 \cdot \log n)</tex>) ==
Вспомним, что по [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|теореме о связи рекурренты ЛРП и многочленов]] наша реккурента эквивалента некому многочлену <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, при этом <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \cdots - c_k \cdot t^k</tex>. Домножим числитель и знаменатель на <tex>Q(-t)</tex>. Новый знаменатель <tex>R(t) = Q(t) \cdot Q(-t)</tex>. При этом <tex>r_n = \sum\limits_{i = 0}^{n} q_i \cdot q_{n - i} \cdot (-1)^{n - i}</tex>. Нетрудно заметить, что при нечётных <tex>n</tex> коэффициенты <tex>r_n</tex> обращаются в <tex>0</tex>, a <tex>r_0 = 1</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> элементов для каждой новой последовательности.
== Источники информации ==
* [https://studfiles.net/preview/5826382/page:21/ Вычисление рекурренты ЛРП с помощью матриц]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящие функции]]
