Sumsets
| Time Limit: 2000MS |
|
Memory Limit: 200000K |
| Total Submissions: 13210 |
|
Accepted: 5300 |
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
Source
做这题时有些被以前的经验束缚了，看完题第一反应是母函数，然后上模板，然后输入1000000等结果，等啊等就是不出结果。。。参考了大牛的解题报告：Click
#include <stdio.h>
#include <string.h>
#define maxn 1000002
int dp[maxn];
int main() {
int i, n;
scanf("%d", &n);
dp[1] = 1;
for(i = 2; i <= n; ++i) {
if(i & 1) dp[i] = dp[i-1];
else dp[i] = dp[i-1] + dp[i/2];
dp[i] %= 1000000000;
}
printf("%d\n", dp[n]);
return 0;
}
POJ2229 Sumsets 【递推】
原文：http://blog.csdn.net/chang_mu/article/details/41173639
