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).
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).
http://blog.csdn.net/u014688145/article/details/71091333
递推式：
- 1
- 2
- 1
- 2
递推思路，
static int MAX_N = 1000000;
static int[] dp = new int[MAX_N+1];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
dp[0] = 1;
for (int i = 1; i <= n;i++){
if ((i & 0x01) == 0){
dp[i] = dp[i/2];
}
dp[i] += dp[i-1];
dp[i] %= 1000000000;
}
System.out.println(dp[n]);
in.close();
}i递增后，相当于把所有的1加在了最前方，而当i为奇数时，无法构成新的2的幂，当i为偶数时，能多出一部分解，而多出的那部分解即为dp[i/2]的值。http://www.hankcs.com/program/cpp/poj-2229-sumsets.html
将一个数N分解为2的幂之和共有几种分法？
定义dp[i]为i的分解方案数。dp[0] = 2 ^ 0 = 1，递推到 N 。若i为偶数，则dp[i] = dp[i / 2] + dp[i - 1] + 1，否则dp[i] = dp[i - 1] + 1。
int dp[1000000 + 1]; // 数字i的分解数int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int N; cin >> N; dp[0] = 1; // 2^0 for (int i = 1; i <= N; ++i) { if ((i & 0x1) == 0) { dp[i] = dp[ i / 2]; // 将i / 2的每个构成数乘以2，得到i } dp[i] += dp[i - 1]; // 将i - 1的构成数拿过来加一 dp[i] %= 1000000000; } cout << dp[N] << endl;#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}
1. n为奇数，则肯定其中有1的组成，所以dp[n] = dp[n-1]
2. n为偶数，根据1的存在划分为2种情况：
a, 有1的组成，则肯定有2个1，dp[n]的一部分是dp[n-2]
b, 没有1的组成，这时候如果把组成的每个数都除以2，则dp[n]的另一部分就变成dp[n/2]
const int M = 1000000000; const int MAXN = 1000010; int dp[MAXN]; int main() { int n; scanf("%d", &n); dp[0] = dp[1] = 1; for (int i = 2; i <= n; ++i) if (i & 0x01) dp[i] = dp[i-1]; else dp[i] = (dp[i-2] + dp[i>>1]) % M; printf("%d\n", dp[n]); return 0; }Read full article from 2229 -- Sumsets
