记忆化搜索

```

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9;
const int N=1e6+10;
int mp[N][30];
bool st[N][30];
int n;

int f(int num,int di){
    if(num==0){
        return 1;
    }    
    if(num<(1<<di))    return 0;
    if(st[num][di])    return mp[num][di];
    int ans=0;
    for(int i=di;(1<<i)<=num;i++){
        ans=(ans+f(num-(1<<i),i))%mod;
    }
    st[num][di]=true;
    mp[num][di]=ans;
    return ans;
}

int main(){
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",f(n,0));
    }
    return 0;
}

```

DP

```

#include<bits/stdc++.h&...