Sumsets

Time Limit : 6000/2000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 45 Accepted Submission(s) : 20

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

Sample Output

6
题意 给定一个n，n又2的幂次方相加得到，问有多少中相加的方式
分析 当n为奇数的时候 就是再前一个的基础上加上1，a[n]=a[n-1]
　　当n为偶数的时候：
　　　　如果加数里含有1，则一定至少有2个1，就是对n-2后面+1+1，就是a[n-2]
　　　　如果加数里面没有1，即对n/2的每一个加数乘以2，总类数为a[n/2]
　　所以n为偶数时的总类数为a[n]=a[n-2]+a[n/2]

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 int a[+];

 int main()

 {

     int n;

     a[]=,a[]=;

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

     {

         if(i%)

         {

             a[i]=a[i-];

         }

         else

         {

             a[i]=a[i-]+a[i/];

             a[i]%=;

         }

     }

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

     {

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

     }

     return ;

 }

巴特西

Sumsets 递推