Sumsets

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1586    Accepted Submission(s): 609

Problem Description

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

7

 

Sample Output

6

 

/* 讨论版 */如果所求的n为奇数，那么所求的分解结果中必含有1，因此，直接将n-1的分拆结果中添加一个1即可 为s[n-1]如果所求的n为偶数，那么n的分解结果分两种情况1. 含有1 这种情况可以直接在n-1的分解结果中添加一个1即可 s[n-1]2. 不含有1，那么分解因子的都是偶数，将每个分解的因子都除以2，刚好是n/2的分解结果，并且可以与之一一对应，这种情况有 s[n/2]所以，状态转移方程：如果i为奇数, s[i] = s[i-1]如果i为偶数，s[i] = s[i-1] + s[i/2]#include 
      
       #define N 1000000#define MOD 1000000000int n,s[N+2];int main(){    s[1]=1;    s[2]=2;    int i=3;    while(i<=N)    {         s[i++]=s[i-1];        s[i++]=(s[i-2]+s[i>>1])%MOD;    }    while(scanf("%d",&n)!=EOF)        printf("%d\n",s[n]);    return 0;}