Изменения

Пусть нам дана линейная реккурента размера <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> времени. Хочется уметь делать это как-то быстреерешать эту задачу. Рассмотрим два способа это сделать. == Первый способ (за <tex>O(k^3 \cdot logn)</tex>) ==