题解 | #整数拆分#

//二维数组过大，爆空间!
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 10010, mod = 1000000000;
//
//int n;
//int f[N][N];
//
//int main()
//{
//    cin >> n;
//    for(int i=0;i<=n;i++) f[i][0] = 1;
//    int i;
//    for (i = 1; i <= n; i *= 2 )
//        for (int j = 0; j <= n; j ++ )
//        {
//            f[i][j] = f[i/2][j];
//            if(j >= i)
//                f[i][j] = (f[i/2][j] + f[i][j - i]) % mod;
//        }
//    cout << f[i/2][n] << endl;
//
//    return 0;
//}
//



#include <iostream>
#include <algorithm>
using namespace std;
//类比于完全背包问题
const int mod = 1000000000,N=1000000;
int n;
int f[N];
int main()
{
    cin >> n;
    f[0] = 1; //如果要求结果为0，只有一种方案，即什么也不选
    for(int i=1;i<=n;i *= 2)
        for(int j=i;j<=n;j++)       
            f[j] = (f[j]+f[j-i]) % mod;
    cout << f[n];
    return 0;
}