Sumsets

Time Limit: 2000MS		Memory Limit: 200000K
Total Submissions: 19024		Accepted: 7431

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). 

A single line with a single integer, N.

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).

7

6

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <climits>

using namespace std;

#define LL long long

const int INF = 0x3f3f3f3f;

const int mod=1000000000;

int dp[1000005];

int main()

{

    int n;

    memset(dp,0,sizeof dp);

    dp[0]=1;

    for(int i=0;i<=20;i++)

    {

        int k=pow(2,i);

        for(int j=k;j<1000005;j++)

        {

            dp[j]=(dp[j]+dp[j-k])%mod;

        }

    }

    while(~scanf("%d",&n)){

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

    }

    return 0;

}

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <climits>

using namespace std;

#define LL long long

const int INF = 0x3f3f3f3f;

const int mod=1000000000;

int dp[1000005];

int main()

{

    int n;

    memset(dp,0,sizeof dp);

    dp[1]=1;

        for(int j=2;j<1000005;j++)

        {

           if(j%2)

            dp[j]=dp[j-1]%mod;

           else

            dp[j]=(dp[j-1]+dp[j/2])%mod;

        }

    while(~scanf("%d",&n)){

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

    }

    return 0;

}