54
правки
Изменения
м
→Разбиение на слагаемые: косметические исправления
Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex>, таких разбиений <tex>\mathtt{d[i - j][j]}</tex>, либо не содержать, таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>.
Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:
<p>
'''int''' part2num(part: '''list<int>'''):
numOfPart = 0
'''for''' i = 1 '''to''' N <font color=green>// <tex>nN</tex> {{---}} число, которое было разбито на слагаемые </font>
'''for''' j = last '''to''' part[i] - 1 <font color=green>// перебираем все элементы, лексикографически меньше нашего, но больше или равны предыдущего</font>
numOfPart += d[N - sum - j][j] <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font>
Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.
== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
