POJ2229 Sumsets

POJ2229 Sumsets

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

1
7

Sample Output

1
6

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>

long long d[1000010];

int main() {
int n;
scanf("%d", &n);
d[0] = 1;
for(int i = 1; i <= n; ++i) {
if(i & 1) {
d[i] = d[i - 1];
} else{
d[i] = (d[i - 1] + d[i >> 1]) % 1000000000;
}
}
printf("%lld\n", d[n]);
return 0;
}

Analysis

  1. 如果 n 是奇数,每一个组合必定有 1,则 dp[n] = dp[n-1]。
  2. 若 n 是偶数,其中有 1 的组合数 dp[n-1],不含 1 的组合,每个数都是 2 的倍数,都除以 2,有 dp[n/2] 个。dp[n] = dp[n-1]+dp[n/2]。
# POJ

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×