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> времени. Хочется уметь как-то быстрее решать эту задачу. Рассмотрим два способа это сделать.
== Первый способ (за <tex>O(k^3 \cdot logn)</tex>) ==
Заметим, что линейные рекурренты хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик.
<tex>A_0 = \begin{pmatrix}
a_{k - 1}\\
a_{k - 2}\\
\vdots \\
a_0
\end{pmatrix}</tex>
Так же выпишем следующую матрицу перехода:
<tex>T = \begin{pmatrix}
c_1 & c_2 & c_3 & \cdots & c_k\\
1 & 0 & 0 & \cdots & 0\\
0 & 1 & 0 & \cdots & 0\\
\vdots & \vdots & \vdots & ~ & \vdots \\
0 & 0 & 0 & \cdots & 1\\
\end{pmatrix}</tex>
Заметим, что умножив <tex>A_0</tex> слева на <tex>T</tex> мы получим столбик <tex>A_1</tex> следующего вида:
<tex>A_1 = T \cdot A_0 = \begin{pmatrix}
a_{k}\\
a_{k - 1}\\
\vdots \\
a_1
\end{pmatrix}</tex>
Аналогично домножив <tex>A_1</tex> слева на <tex>T</tex> получим
<tex>A_2 = T \cdot A_1 = \begin{pmatrix}
a_{k + 1}\\
a_{k}\\
\vdots \\
a_2
\end{pmatrix}</tex>
Продолжая так для любого <tex>i</tex> мы получим столбик <tex>A_i</tex> состоящий из <tex>k</tex> подряд идущий членов последовательности, начиная с <tex>a_i</tex>
