[Usaco2005 Jan]Sumsets 求和

[Usaco2005 Jan]Sumsets 求和

给出一个N(1≤N≤10^6)，使用一些2的若干次幂的数相加来求之．问有多少种方法

Input
一个整数N.

Output
方法数．这个数可能很大，请输出其在十进制下的最后9位．

Sample Input
7
Sample Output
6

六种方式
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

发现如果x是2的倍数则可以拆成x-1与x/2

为什么？拆成x-1相当于给(x-1)的每个方案+1，就变成了又一种方案了

拆成x/2相当于给x/2的每个方案*2 就变成了另一种方案了

仔细一想并不会重复，因为第一种情况每个方案必然带1，

而第二种情况每个方案必然不带1

再想想发现并不会重复，因为含1、含2的情况都存在

为什么不能从x-2递推上来？(x-2),因为x-2方案中可能有带2的情况

而2+2是一种，合并起来又可以产生个4，就变成两种了

int n,a[1000001];
int main(){
    scanf("%d",&n);
    a[1]=1;
    for(int i=2;i<=n;i++){
        a[i]=a[i-1];
        if(!(i&1))a[i]=a[i-1]+a[i>>1];
        a[i]%=1000000000;
    }
    printf("%d",a[n]); 
    return 0;
}