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>k</tex> первых членовпоследовательности. Требуется уметь вычислять произвольное <tex>a_n</tex>.
Самый простой способ сделать это {{---}} последовательно считать каждый <tex>a_i</tex>, пока <tex>i</tex> не сравняется с <tex>n</tex>. Однако этот способ не самый эффективный, ведь он, очевидно, требует <tex>O(n \cdot k)</tex> времени. Хочется уметь как-то быстрее решать эту задачу. Рассмотрим два способа это сделать.
