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

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

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

Умножение матриц (за $O(k^3 \cdot \log n)$)

Заметим, что ЛРП хорошо выражаются через матрицы. Запишем наши первые $k$ членов последовательности в столбик. $A_0 = \begin{pmatrix} a_{k - 1}\\ a_{k - 2}\\ \vdots \\ a_0 \end{pmatrix}$ Так же выпишем следующую матрицу перехода: $T = \begin{pmatrix} c_1 & c_2 & c_3 & \cdots & c_{k - 1} & c_k\\ 1 & 0 & 0 & \cdots & 0 & 0\\ 0 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & ~ & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0\\ \end{pmatrix}$

Заметим, что умножив $T$ на $A_0$, мы получим столбик $A_1$ следующего вида: $A_1 = T \cdot A_0 = \begin{pmatrix} a_{k}\\ a_{k - 1}\\ \vdots \\ a_1 \end{pmatrix}$ Аналогично, домножив $T$ на $A_1$, получим $A_2 = T \cdot A_1 = \begin{pmatrix} a_{k + 1}\\ a_{k}\\ \vdots \\ a_2 \end{pmatrix}$

Продолжая так, для любого целого неотрицательного $i$, мы получим столбик $A_i$, состоящий из $k$ подряд идущих членов последовательности, начиная с $a_i$. Пользуясь ассоциативностью произведения матриц, можно записать, что $A_i = T^i \cdot A_0$. Из этого соотношения вытекает алгоритм вычисления произвольного $a_n$:

1. Инициализировать матрицы $A_0$ и $T$
2. Возвести матрицу $T$ в степень $n$
3. Посчитать $A_n$ как $T^n \cdot A_0$ и взять из него $a_n$

Используя быстрое возведение в степень во втором пункте, мы будем тратить $O(k^3 \cdot \log n)$ времени. Умножение же в третьем пункте выполняется за $O(k^2)$.

Итого мы получили алгоритм, работающий за $O(k^3 \cdot \log n)$.

Связь с многочленами (за $O(k^2 \cdot \log n)$)

Вспомним, что по теореме о связи ЛРП и многочленов наша ЛРП эквивалента некому отношению многочленов $A(t) = \dfrac{P(t)}{Q(t)}$, при этом $Q(t) = q_0 + q_1 \cdot t + \cdots q_k \cdot t^k = 1 - c_1 \cdot t - c_2 \cdot t^2 - \cdots - c_k \cdot t^k$. Домножим числитель и знаменатель на $Q(-t)$. Новый знаменатель $R(t) = Q(t) \cdot Q(-t)$. При этом $r_n = \sum\limits_{i = 0}^{n} q_i \cdot q_{n - i} \cdot (-1)^{n - i}$. Нетрудно заметить, что при нечётных $n$ коэффициенты $r_n$ обращаются в $0$, a $r_0 = 1$.

Отсюда мы получаем, что многочлен $R(t)$ имеет вид: $R(t) = 1 + r_2 \cdot t^2 + r_4 \cdot t^4 + \cdots + r_{2k} \cdot t^{2k}$. Однако вспомним о связи с ЛРП, тогда мы получили, что $a_n = -r_2 \cdot a_{n - 2} - r_4 \cdot a_{n - 4} - \cdots - r_{2k} \cdot a_{n - 2k}$

Иными словами мы получили новое рекуррентное соотношение для данной последовательности, где каждый элемент зависит от элементов с номерами, имеющими такую же чётность, что номер исходного. То есть по сути наша последовательность разделилась на две независимых: с чётными и нечётными номерами. Можно сказать, что мы теперь ищем не $a_n$ из исходной последовательности, а $a'_{n~div~2}$ из подпоследовательности элементов c номерами, имеющими ту же чётность, что и $n$. Заметим, что этот процесс можно проделывать далее пока $n \geqslant k$, ведь в итоге искомый элемент окажется среди $k$ первых. Всё, что нам нужно,— поддерживать первые $k$ элементов для каждой новой последовательности.

Исходя из всего вышесказанного получаем алгоритм:

   get_nth(n, a[], $Q$) 
       while n $\geqslant$ k
            for i = k to 2k - 1
                a[i] = $\sum\limits_{j = 1}^{k}$ -q[j] $\cdot$ a[i - j]
            $R = Q(t) \cdot Q(-t)$
            filter a[i] with (i mod 2 == n mod 2)
            $Q = R(\sqrt{t})$
            n = n div 2
       return a[n]

Вычисление $a[k], a[k + 1], \cdots , a[2k - 1]$ занимает $O(k^2)$ времени, ибо их всего $k$, а каждый считается за $O(k)$. Умножение многочленов длины порядка $k$ также занимает $O(k^2)$ времени. Итераций внешнего цикла будет $O(\log n)$ в силу того, что мы делим $n$ на $2$ каждый раз.

Итого мы получили алгоритм, работающий за $O(k^2 \cdot \log n)$

См. также

• Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности
• Производящая функция

Источники информации

• Вычисление ЛРП с помощью матриц