hdu 2709 Sumsets

題意：

把n拆成幾個數的和，這些數要是等於2^x的正整數。

代碼：
 
#include<stdio.h> 
__int64 i,a[1000001]={1,1,2}; 
int main() 
{ 
    for(i=3;i<1000001;i++) 
    { 
        if((i&1)==1) 
        { 
            a[i]=a[i-1];    //i為奇數與它前一個數量相同 
        } 
        else 
        { 
            a[i]=(a[i-2]+a[i>>1])%1000000000;    //含有1: a[i-1]每種情況填11、不含1: a[i/2]每種情況*2 
        } 
    } 
    while(scanf("%I64d",&i)!=EOF) 
    { 
        printf("%I64d\n",a[i]); 
    } 
    return 0; 
}