题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2709
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).
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
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 <= 1,000,000）的所有可能表示。
输入
带单个整数的单行，N
输出
将N表示为表示总和的方式的数量。 由于这个号码可能有很大的尺寸，只能打印最后9位数字（以10为底数表示）。
解题思路：这是一道找规律的数学题，意思就是给定一个数N，找出所有1~N中是2的整数次幂的因子的和，（因子可以重复）。
简单举个栗子：当N=3时，有1+1+1=3；1+2=3，共两种情况，所以按照这样的规则，多找出后面几个数，即可找到规律。其规律如下：
数字N= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
总和为N的方式数:1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36...
由以上规律可得当N为奇数时，a[i]=a[i-1]%mod;（i是数字）
当N为偶数时,a[i]=(a[i-1]+a[i/2])%mod;（i>=2）（mod=1e9）
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,a[1000010]; 4 int main() 5 { 6 a[1]=1,a[2]=2; 7 for(int i=3;i<1000010;i++){ 8 if(i%2)a[i]=a[i-1]%1000000000;//奇数 9 else a[i]=(a[i-1]+a[i/2])%1000000000;//偶数 10 } 11 while(cin>>n) 12 cout<<a[n]<<endl; 13 return 0; 14 }