Sumsets POJ
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).
Sample Input
7
Sample Output
6
百度翻译：
农场主约翰命令他的牛寻找不同的数字集合，这些数字加起来就是一个给定的数字。奶牛只使用整数幂为2的数字。以下是总和为7的可能数字集：
1）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
帮助FJ计算给定整数n（1<=n<=1000000）的所有可能表示的方法数。由于这个数字可能很大，所以只能打印最后9位数字。
思路：仔细思考后会得出一个结论：如果这个数是奇数，等于这个数减一所得偶数的所有式 子都加一，所以式子个数不变；如果这个数是偶数，相当于n-2对应的式子数加上n/2对应的式子数的和。注意结果比较大，只输出后九位。
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 1000000007 16 #define eps 1e-6 17 #define ll long long 18 #define INF 0x3f3f3f3f 19 using namespace std; 20 21 int n; 22 int sz[1000005]; 23 int main() 24 { 25 scanf("%d",&n); 26 sz[1]=1; 27 sz[2]=2; 28 for(int i=3;i<=n;i++) 29 { 30 if(i%2!=0) 31 { 32 sz[i]=sz[i-1]; 33 } 34 else 35 { 36 sz[i]=sz[i-2]+sz[i/2]; 37 } 38 sz[i]=sz[i]%1000000000; 39 } 40 printf("%d",sz[n]); 41 }