89
правок
Изменения
Нет описания правки
Пусть нам дана [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#def_linear.|линейная рекуррентная последовательность]] (далее ЛРП) порядка <tex>k</tex>. А именно: <tex>a_n = c_1 \cdot a_{n - 1} + c_2 \cdot a_{n - 2} + \cdots + c_k \cdot a_{n - k}</tex> при <tex>n \geqslant k</tex>, а так же заданы <tex>k</tex> первых членов последовательности. Требуется уметь вычислять произвольное <tex>a_n</tex>.
Самый простой способ сделать это {{---}} последовательно считать каждый <tex>a_i</tex>, пока <tex>i</tex> не станет равен <tex>n</tex>. Однако этот способ не самый эффективный, он, очевидно, требует <tex>O(n \cdot k)</tex> времени, но можно сделать это быстрее. Рассмотрим два способа это сделать.
