89
правок
Изменения
→Связь с многочленами (за O(k^2 \cdot logn))
Исходя из всего вышесказанного получаем алгоритм:
get_nth(n, a[], <tex>Q<code/tex>) { '''while''' (n <= tex>\geqslant</tex> k) { count calculate a[k], a[k + 1], ...<tex>\cdots</tex>, a[2k - 1]; <tex>Q(t) = Q(t) * \cdot Q(-t)</tex>; leave a[i] with (i % 2 == n % 2); <tex>Q = Q: (\sqrt{t^2i -})</tex> t^i; 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(logn)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз.
