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>n \geqslant 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\log n)</tex>) ==
Заметим, что линейные рекурренты хорошо выражаются через матрицы. Запишем наши первые <tex>k</tex> членов последовательности в столбик.
# Посчитать <tex>A_n</tex> как <tex>T^n \cdot A_0</tex> и взять из него <tex>a_n</tex>
Используя быстрое возведение в степень во втором пункте, мы будем тратить <tex>O(k^3 \cdot logn\log n)</tex> времени. Умножение же в третьем пункте выполняется за <tex>O(k^2)</tex>.
Итого мы получили алгоритм за <tex>O(k^3 \cdot logn\log n)</tex>.
== Связь с многочленами (за <tex>O(k^2 \cdot logn\log n)</tex>) ==
Вспомним, что по [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|теореме о связи рекурренты и многочленов]] наша реккурента эквивалента некому многочлену <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, при этом <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \cdots - c_k \cdot t^k</tex>. Домножим числитель и знаменатель на <tex>Q(-t)</tex>. Новый знаменатель <tex>R(t) = Q(t) \cdot Q(-t)</tex>. При этом <tex>r_n = \sum\limits_{i = 0}^{n} q_i \cdot q_{n - i} \cdot (-1)^{n - i}</tex>. Нетрудно заметить, что при нечётных <tex>n</tex> коэффициенты <tex>r_n</tex> обращаются в <tex>0</tex>, a <tex>r_0 = 1</tex>.
}
Вычисление <tex>a[k], a[k + 1], \cdots , a[2k - 1]</tex> занимает <tex>O(k^2)</tex> времени, ибо их всего <tex>k</tex>, а каждый считается за <tex>O(k)</tex>. Умножение многочленов длины порядка <tex>k</tex> также занимает <tex>O(k^2)</tex> времени. Итераций внешнего цикла будет <tex>O(logn\log n)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз.
Итого мы получили алгоритм, работающий за <tex>O(k^2 \cdot logn\log n)</tex>
==См. также==
