1679
правок
Изменения
м
Расммотрим Рассмотрим бесконечное произведение
Нет описания правки
== Алгоритм за n sqrt(n) ==
Рассмотрим самый адовый и самый быстрый алгоритм их нахождения - за <tex> O(n \sqrt{n}) </tex>. Если кто хочет добавить другие алгоритмы, добавьте.
Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.
<tex> (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots </tex>
Каждый член произведения получается в результате умножения мономов(одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex>x^{m_1}</tex>, во второй — <tex>x^{2m_2}</tex> и т.д., то их произведение будет равно <tex>x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex>x^{m_1 + 2m_2 + 3m_3 + \dots}</tex>.
