> poj 2229 Sumsets
> //解题报告
> /*
> 题意:给出一个整数n,求解该整数n有多少种由2的幂次之和组成的方案.
> 解题思路：
> 1.可以将n用二进制表示.
> n=1,只有1种表示方法。
> n=2，10(2)，二进制表示下，可以分拆成{1,1}，{10}有两种表示方法
> n=3, 11(2),可以分拆成{1,1,1},{10,1}.
> n=4, 100(2),{1,1,1,1},{10,1,1},{10,10},{100}.
> 总结：如果所求的n为奇数，那么所求的分解结果中必含有1，因此，直接将n-1的分拆结果中添加一个1即可 为s[n-1]
> 如果所求的n为偶数，那么n的分解结果分两种情况
> 1.含有1 这种情况可以直接在n-1的分解结果中添加一个1即可 s[n-1]
> 2.不含有1 那么，分解因子的都是偶数，将每个分解的因子都除以2，刚好是n/2的分解结果，并且可以与之一一对应，这种情况有 s[n/2]
> 
> */
> #include<stdio.h>
> #include<string.h>
> 
> int a[1000010];
> int main()
> {
>     a[1]=1;
>     a[2]=2;
>     int n,i=3;
>     while(i<=1000000){
>             a[i++]=a[i-1];
>             a[i++]=(a[i-1]+a[i>>1])%1000000000;
>     }
>     while(scanf("%d",&n)!=EOF){
>         printf("%d\n",a[n]);
>     }
>     return 0;
> }