89
правок
Изменения
→Связь с многочленами (за O(k^2 \cdot \log n))
== Связь с многочленами (за <tex>O(k^2 \cdot \log n)</tex>) ==
Вспомним, что по [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности|теореме о связи ЛРП и многочленов]] наша ЛРП эквивалента некому отношению многочленов <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, при этом <tex>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</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>R(t)</tex> имеет вид: <tex>R(t) = 1 + r_2 \cdot t^2 + r_4 \cdot t^4 + \cdots + r_{2k} \cdot t^{2k}</tex>. Однако вспомним о связи с ЛРП, тогда мы получили, что <tex>a_n = -r_2 \cdot a_{n - 2} - r_4 \cdot a_{n - 4} - \cdots - r_{2k} \cdot a_{n - 2k}</tex>
Исходя из всего вышесказанного получаем алгоритм:
get_nth(n, a[], <tex>Q</tex>) { '''while''' (n <tex>\geqslant</tex> k) { '''for''' (i = k<tex>\cdots</tex>'''to''' 2k - 1) {
a[i] = <tex>\sum\limits_{j = 1}^{k}</tex> -q[j] <tex>\cdot</tex> a[i - j]
<tex>R = Q(t) \cdot Q(-t)</tex>
'''filter ''' a[i] '''with ''' (i '''mod ''' 2 == n '''mod ''' 2)
<tex>Q = R(\sqrt{t})</tex>
n = n '''div ''' 2 } '''return ''' a[n] }
Вычисление <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(\log n)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз.
