题目：HDOJ-2709
题目描述：
给出一个正整数N，求出N能由多少种2的幂次方（1，2，4，8…）之和的组合得到。
（1 <= N <= 1,000,000）（由于数据过大，所有答案只取后9位。）
例如当N等于7，有6种方案
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
思路：
当N为奇数（分解方案中必有1）：则N-1为偶数，易知N的所有分解方案都是在N-1的基础上+1
所以此时f(N)=f(N-1)
当N为偶数：
①首先同样的在N-1的所有分解方案上+1，可以得到部分的分解方案。
②但是，还是存在分解方案内不含1的情况，经分析可以知道将N/2的所有分解方案*2，就得到了所有不含1的分解方案。
所以此时f(N)=f(N-1)+f(N/2)
举个例子便于理解：
N=2，2种方案：①2 ②1+1
N=3，2种方案：①2+1 ②1+1+1
可以看到N=3时，都是在N=2的基础上+1。
那么当N=4时，
首先是在N=3的基础上+1，得到两种：①2+1+1 ②1+1+1+1
再者就是将N=2的方案*2，又得到两种：③4 ④2+2
一共4种方案
+1提供了包含1的方案，*2提供了不包含1的方案，两者得到依旧是2的幂次方的求和组合。
以下代码：
#include<cstdio>
using namespace std;
int main()
{
__int64 f[1000001];int i,n;f[1] = 1;f[2] = 2;for (i = 3; i <= 1000000; i++){
if (i % 2 == 1)f[i] = f[i - 1]; //为奇数elsef[i] = f[i - 1] + f[i / 2]; //为偶数f[i] %= 1000000000; //取最后9位}while (scanf("%d", &n)!=EOF)printf("%I64d\n", f[n]);return 0;
}