Тема: Сумма степеней двойки
http://acmp.ru/index.asp?main=task&id_task=525
Какую тут динамику можно использовать и можно ли какую-ту формулу придумать?!
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Сумма степеней двойки
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
http://acmp.ru/index.asp?main=task&id_task=525
Какую тут динамику можно использовать и можно ли какую-ту формулу придумать?!
Можно такую динамику:
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))
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Сумма степеней двойки