http://poj.org/problem?id=2229
题意：
大体上是说给定一个n，问n能被拆成多少种2的幂次之和
思路：
这题和以前做过的一道数的划分很像，可以说基本一样，姑且算是dp吧。这里有个比较特殊的地方，就是n是要拆分成2的幂次，所以奇数和偶数得分开讨论。f[n]表示数字n能被拆成的2的幂次之和的种数。当n为奇数时，f[n] = f[n-1],这个显而易见，当n为奇数时，他的拆法和n-1的拆法相同，只需要在n-1的拆法上加1，当n为偶数时f[n] = f[n/2] + f[n-1],相当于n/2的情况里每项依次乘2，但是这样，以1开始的情况都被排除在外了，也就是n-1第一项加1的情况，所以还要加上f[n-1]。这题只需要输出答案的最后9位，一开始没看到，一激动没有mod，然后就。。。。
代码：
#include <cstdio>
#include <cstring>const int mod = 1000000000;int f[1000000 + 10];int main()
{int n;while(~scanf("%d", &n)){memset(f, 0, sizeof(f));f[1] = 1;for(int i = 2; i <= n; i++)if(i % 2 == 0)f[i] = (f[i / 2] + f[i - 1]) % mod;elsef[i] = f[i - 1] % mod;printf("%d\n",f[n]);}return 0;
}