POJ 2229 Sumsets（找规律，预处理）

/*
8=1+1+1+1+1+1+1+1+1   1
8=1+1+1+1+1+1+1+2      2 3
8=1+1+1+1+2+2             
8=1+1+1+1+4                4 5
8=1+1+2+2+2               
8=1+1+2+4                   6 7
8=2+2+2+2
8=2+2+4
8=4+4
8=8                             8~9
*/
/*
以下引用自博客：http://blog.csdn.net/scorpiocj/article/details/5940456
如果i为奇数，肯定有一个1，把f[i-1]的每一种情况加一个1就得到fi,所以f[i]=f[i-1]
如果i为偶数，如果有1，至少有两个，则f[i-2]的每一种情况加两个1，就得到i，如果没有1，则把分解式中的每一项除2，则得到f[i/2]
所以f[i]=f[i-2]+f[i/2]
由于只要输出最后9个数位，别忘记模1000000000
*/

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

int a[1000010];

int main()
{
    a[1]=1;a[2]=2;
    for(int i=3;i<1000010;i++)
    {
        if(i%2)a[i]=a[i-1];
        else a[i]=(a[i-2]+a[i/2])%1000000000;
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",a[n]);
    }
    return 0;
}