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;
}

• Re:解题报告 (810) BinFeng 2015-06-22 09:41:37
  • Re:解题报告 (12) 2018629 2018-07-05 10:45:27
• Re:解题报告 (804) qunideba 2019-08-24 16:04:13