1

Тема: Сумма степеней двойки

http://acmp.ru/index.asp?main=task&id_task=525
Какую тут динамику можно использовать и можно ли какую-ту формулу придумать?!

2 Отредактировано cmd (2011-08-01 21:34:56)

Re: Сумма степеней двойки

Можно такую динамику:
f(n, last) = count - количество таких разложений в сумму степеней двоек, что последнее из слагаемых last. Тогда ответ сумма по last для n.
Рекуррентность такая: f(n, last) = sum(f(n - last, i), i <= last и i - степень двойки), база динамики: f(2^i, 2^i) = 1.
Можно ускорить ДП, если считать не количество разложений, что последнее из слагаемых last, а количество разложений, что последнее не больше last.


*Ну и вторым параметром можно просто степень двойки сохранять, а не само число. Сложность будет что-то типа O(N * log(N))