89
правок
Изменения
→Связь с многочленами (за O(k^2 \cdot \log n))
Исходя из всего вышесказанного получаем алгоритм:
get_nth(n, a[], <tex>Q</tex>) { '''while''' (n <tex>\geqslant</tex> k) { '''for''' (i = k<tex>\cdots</tex>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
Вычисление <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> каждый раз.
