Sumsets

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

Total Submission(s): 3094 Accepted Submission(s): 1225

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

题意：

　　给你一个n，要你把n分解成只含有2^n的数的和。求有多少种方法。

题解：

　　写一下前几项，1 2 2 4 4 6 6 10 10。这就是1~9。

　　我们可以发现比如说像

　　2 = { 1 1， 2 } 两种 3 = {1 1 1， 2 1}。很明显2和3是属于一类的。应为多了一个1无法合并出多一个2。

　　7 = {1 1 1 1 1 1 1, 而（6，7）相对与前面一个（4，5 ）来说 5 = { 1 1 1 1 1,[ 1, 1] 有4种情况个是相当于直接在后面加上两个1实现的。所以我们可以推测出 dp[i] = dp[i-2] + x。

　　　　1 1 1 1 1 2　　　　　　　　　　　　　　　　　　　　　　　　　 1 1 1 2, [1, 1]

　　　　1 1 1 2 2　　　　　　　　　　　　　　　　　　　　　　　　　　 1 2 2 [1, 1]

　　　　1 1 1 4　　　　　　　　　　　　　　　　　　　　　　　　　　　 1 4 [1, 1]

　　　　1 2 2 2　　　　　　　　　　　　　　　　　　　　　　　　　　　}

　　　　1 2 4}

　　而那个x 是多少呢。

　　7对5来说多了 {1 2 2 2， 1 2 4} 这两个数。因为6和7是一个整体，我们也就可以认为是多了 {2 2 2， 2 4} 这两个数（用4和6去比较）

　　而{2 2 2, 2 4} 这两个数十分的像 3 ={1 1 1， 1 2}。只是将 1 换成了 2 ，将2换成了4。

　　所以我们不难看出 dp[(6/7)] = dp[(4,5)] + dp[3]。

　　所以 dp[i] = dp[i-2] + dp[i/2]。

　　有了这个直接跑就可以了，i只有1000000.

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 using namespace std;13 typedef long long LL;14 typedef unsigned long long uLL;15 #define ms(a, b) memset(a, b, sizeof(a))16 #define pb push_back17 #define mp make_pair18 #define eps 0.000000000119 const LL INF = 0x7fffffff;20 const int inf = 0x3f3f3f3f;21 const int mod = 1000000000;22 const int maxn = 1000000+10;23 int dp[maxn];24 int main() {25 #ifdef LOCAL26 freopen("input.txt", "r", stdin);27 // freopen("output.txt", "w", stdout);28 #endif29 ios::sync_with_stdio(0);cin.tie(0);30 ms(dp, 0);31 dp[0] = 1;32 dp[1] = 1;33 for(int i = 2;i
                 
                  > n){38 cout << dp[n] << endl;39 }40 return 0;41 }

View Code

转载于:https://www.cnblogs.com/denghaiquan/p/7260531.html

你可能感兴趣的文章