2229. Sumsets

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:

1) 1+1+1+1+1+1+1

2) 1+1+1+1+1+2

3) 1+1+1+2+2

4) 1+1+1+4

5) 1+2+2+2

6) 1+2+4

Help FJ count all possible representations for a given integer n (1 ≤ n ≤ 1,000,000).

Input. A single line with a single integer n.

Output. The number of ways to represent n as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

Sample input	Sample output
7	6

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть f(n) содержит количество представлений числа n в виде суммы степеней двойки. Тогда:

· f(1) = 1, имеется одно разложение: 1 = 1;

· f(2) = 2, имеется два разложения: 2 = 2, 2 = 1 + 1;

Если число n нечетное, то оно обязательно в своем разложении должно иметь единицу и f(n) = f(n – 1).

Если число n четное, то можно либо вычленить из него слагаемое 1 и далее рассмотреть количество разбиений числа n – 1 в виде требуемых сумм, либо получить все разбиения числа n / 2 и умножить каждое его слагаемое на 2. Откуда f(n) = f(n / 2) + f(n – 1).

Реализация алгоритма

#include <stdio.h>

#define MAX 1000010

#define MOD 1000000000

int i, n;

int dp[MAX];

int main(void)

{

scanf("%d",&n);

dp[1] = 1; dp[2] = 2;

for(i = 3; i<= n; i++)

if (i % 2 == 0)

dp[i] = (dp[i/2] + dp[i-1]) % MOD;

else

dp[i] = dp[i-1];

printf("%d\n",dp[n]);

return 0;

}