完全可以把n加强到1e8，因为空间和时间复杂度都是O(n/2).

解题报告：
f[i]表示i分解成若干2的幂次的和的方案数. 
i=     0 1 2 3 4 5 6 7 ...
f[i]=  0 1 2 2 4 4 6 6 ...
规律: 若i为奇数,则f[i]=f[i-1];
      若i为偶数,则f[i]=f[i-1]+f[i/2].
证明: 若i为奇数,则必有1,因为1=2^0,所以减一后得f[i-1],
            并且无其他可能拆分的情况.
      若i为偶数,则:
		取一个1出来,则f[i]=f[i-1];
		不取1出来,则因为i为偶数,f[i]=f[i/2].
综上,有:
f[0]=0,f[1]=1;
转移方程:f[i]=f[i-1]+((!(i%2))?f[i/2]:0).

------------不怎么华丽的分割线------------ 

这样就可以过了，但是如果n<=1e8,就不可以定义1e8的数组.
那么利用i为奇数时f[i]=f[i-1],定义f[N/2]的数组, 
并且可得:
若i=1,则特判（或可以设f[0]=1，就不用特判了）;
若i>1,则首先由1(0和1共用0)到n/2计算出f,
	  然后算出f[n/2]即可. 

贴代码：
#include<iostream>
#define N 500009
//n=1e8时：#define N 50000009
#define mod 1000000000
using namespace std;
int n,f[N]={1};
int main() {
	cin>>n;
	for (int i=1;i<=n/2;i++)
		f[i]=(f[i-1]%mod+f[i/2]%mod)%mod;
	cout<<f[n/2]%mod<<endl;
	return 0;
}