Быстрое вычисление членов линейной рекуррентной последовательности

Пусть нам дана линейная реккурента размера [math]k[/math]. А именно: [math]a_n = c_1 \cdot a_{n - 1} + c_2 \cdot a_{n - 2} + \cdots + c_k \cdot a_{n - k}[/math], а так же заданы [math]k[/math] первых членов. Требуется уметь вычислять произвольное [math]a_n[/math].

Самый простой способ сделать это — последовательно считать каждый [math]a_i[/math], пока [math]i[/math] не сравняется с [math]n[/math]. Однако этот способ не самый эффективный, ведь он, очевидно, требует [math]O(n \cdot k)[/math] времени. Хочется уметь как-то быстрее решать эту задачу. Рассмотрим два способа это сделать.