题目链接：http://poj.org/problem?id=2229
题目大意：任意给出一个数字n，要求将这个数字分解成若干2的幂数相加，求可以分解的情况数。
解题思路：递推，写出前几个数的分解数后发现规律，若数字为奇数，则情况数等于它前面的那个偶数的情况数，若为偶数，则等于它之前两位的情况数加上它除以2之后的情况数。
AC代码：
#include <iostream>
#include <cmath>
using namespace std;
long long num[1000005];
int main()
{int n;num[1]=1;num[2]=2;for(int i=3;i<=1000000;i++){if(i%2==0){num[i]=num[i-2]+num[i/2];}else num[i]=num[i-1];num[i]%=1000000000;}while(cin>>n){cout<<num[n]<<endl;}return 0;
}