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