题意：给定一个整数N （1<= N <= 1000000），求出以 N为和 的式子有多少个，式子中的加数只能有2的幂次方组成
如5 : 1+1+1+1+1、1+1+1+2、1+2+2、1+4，共有5个
思路：当N为奇数时，N的式子中都必有1，故知只需在N-1的式子中都+1就可以，即d[N] = d[N-1]
当N为偶数时，N的式子可以分为，有1 或者 没1：有1的式子，必有2个1，那么可以由N-2的式子加上两个1；
没有1的式子，把式子中的加数都除以2，故可以由N/2的式子求得。
AC代码：
#include <cstdio>
using namespace std;
const int N = 1000005;
const int MOD = 1000000000;
int d[N],n;
int main()
{
d[1] = 1;
d[2] = 2;
for(int i = 3; i <= N-5; i++)
{
if(i%2) d[i] = d[i-1];
else d[i] = d[i-2] + d[i/2];
d[i] %= MOD;
}
while(~scanf("%d", &n))
{
printf("%d\n", d[n]);
}
return 0;
}