89
правок
Изменения
Нет описания правки
Отсюда мы получаем, что многочлен <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>
Иными словами мы получили новое рекуррентное соотношение для данной последовательности, где каждый элемент зависит от элементов с номерами, имеющими такую же чётность, что номер исходного. То есть по сути наша последовательность разделилась на две независимых: с чётными и нечётными номерами. Можно сказать, что мы теперь ищем не <tex>a_n</tex> из исходной последовательности, а <tex>a'_{n~div~2}</tex> из подпоследовательности элементов, имеющих ту же чётность, что и <tex>n</tex>. Заметим, что этот процесс можно проделывать далее пока <tex>n \geqslant k</tex>, ведь в итоге искомый окажется среди <tex>k</tex> первых. Всё, что нам нужно,{{---}} поддерживать первые <tex>k</tex> элементов для каждой новой последовательности.
Исходя из всего вышесказанного получаем алгоритм:
<code>
'''while''' (n <= k) {
count a[k], a[k + 1], ..., a[2k - 1];
Q(t) = Q(t) * Q(-t);
leave a[i] with (i % 2 == n % 2);
Q: t^2 -> t;
n = n div 2;
}
return a[n];
</code>
