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

Пусть нам дана линейная реккурента размера [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]a_n[/math].

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