Задача “Суммы” (Рекуррентные соотношения с одним параметром)

Условие задачи:  ссылка
Основная идея:  Идея, предложенная автором, помогает прочувствовать задачу максимально эффективно. Опишу ее вкратце (когда перечитывал пост целиком, улыбнуло слово “вкратце”):
1)  Итак, ручками составляем ответы для N в интервале от [1,8].
2) Обозначим  K(i) – ответ на задачу, т.е. количество разложений числа i на слагаемые, которые являются степенями двойки
3) Рассмотрим ответы, составленные на пункте 1) для N=4 и N=5.

N = 4	N=5
4	4+1
2+2	2+2+1
2+1+1	2+1+1+1
1+1+1+1	1+1+1+1+1

Что может сразу броситься в глаза? Столбцы чем-то похожи: а именно тем, что элементы второго столбца получаются из соответствующих элементов первого столбца прибавлением единицы. Таким образом делаем вывод, что K(i) = K(i-1), если i – нечетное. В справедливости этого утверждения можно убедиться и на других нечетных элементах.  
4) Для полного решения задачи нам осталось найти рекуррентное соотношение для четного i. Эта задача будет посерьезней. Пойдем тем же путем: рассмотрим ответы для N=5 и N=6.

N=5	N=6
4+1	4+2
2+2+1	(!) 4+1+1
2+1+1+1	2+2+2
1+1+1+1+1+1	(!) 2+2+1+1
	(!) 2+1+1+1+1
	(!) 1+1+1+1+1+1

Пометим знаком (!) во втором столбце те элементы, которые были получены с помощью того же правила, что и в пункте 3), а именно увеличением на единицу элемента из первого столбца. После этой процедуры осталось два разложения:

4+2

2+2+2

Как найти количество этих разложений?
5) Размышления: Наверное это самый интересный и сложный момент в задаче. Опытные олимпиадчики скорее всего со мной не согласятся, подсчитав, что это рабочий момент, который не должен вызывать трудностей. Но именно поэтому такие люди наделены идентификатором “опытные”. За их плечами сотни решенных задач с тимуса и им не нужно рассказывать про рекуррентные соотношения. Михаил Долинский во введении к этой теме высказал мнение о том, что составление рекуррентных соотношений это искусство, овладеть которым поможет рассмотрение и самостоятельно решение группы задач на эту тему. Вот как раз такой момент искусства применен для решения пункта 5)
По существу: Отметим тот факт, что полученные элементы в конце пункта 4) являются четными. Поделим каждый элемент разложений на 2, получим:

2+1

1+1+1

И о чудо! Мы получили разложения для N=3. Следовательно получаем рекуррентное соотношение K(i) = K(i-1) + K(i/2), если i-четно. Как и раньше в справедливости этого подхода можно убедиться на других четных элементах N, например на восьмерке.

Исходный код: здесь 

P.S: Для успешного решения задачи необходимо прочувствовать пункты 1) и 5).