Give me the answer （C++代码）内存超限，仅供参考

解题思路:
0
1 1
2 2    1+1
3 2+1  1+1+1
4 4    2+2     2+1+1   1+1+1+1
5 4+1  2+2+1   2+1+1+1 1+1+1+1+1
6 4+2  4+1+1   2+2+2   2+2+1+1     2+1+1+1+1   1+1+1+1+1+1



0 : 1  0  0  0  0  0  0  0  0  0
1 : 1  0  0  0  0  0  0  0  0  0
2 : 1  1  0  0  0  0  0  0  0  0
3 : 1  1  0  0  0  0  0  0  0  0
4 : 1  2  1  0  0  0  0  0  0  0
5 : 1  2  1  0  0  0  0  0  0  0
6 : 1  3  2  0  0  0  0  0  0  0
7 : 1  3  2  0  0  0  0  0  0  0


0 : 1  0  0  0  0  0  0  0  0  0
1 : 1  0  0  0  0  0  0  0  0  0
2 : 1  2  0  0  0  0  0  0  0  0
3 : 1  2  0  0  0  0  0  0  0  0
4 : 1  3  4  0  0  0  0  0  0  0
5 : 1  3  4  0  0  0  0  0  0  0
6 : 1  4  6  0  0  0  0  0  0  0
7 : 1  4  6  0  0  0  0  0  0  0



1  1
       1
2  1+1
       2
       1+1
4  1+2+1
       4
       2+2 2+1+1
       1+1+1+1
6  2+3+1=6
       4+2 4+1+1
       2+2+2 2+2+1+1 2+1+1+1+1
       1+1+1+1+1+1
8  1+4+4+1=10
       8
       4+4 4+2+2 4+2+1+1 4+1+1+1+1
       2+2+2+2 2+2+2+1+1 2+2+1+1+1+1 2+1+1+1+1+1+1
       1+1+1+1+1+1+1+1

参考代码:

#include <iostream>

using namespace std;

int map[1000001][21] = {0};//(1,000,000)10=(F4240)16

int main() {
    int T, N;
    int i, j, k, l;
    //预处理，打表
    map[0][0] = 1;
    for (i = 1; i < 1000001; ++i) {
        l = 1;
        for (j = 0; l <= i; ++j, l *= 2) {//拆分出l=2^j
            map[i][j] = map[i - l][j];
        }
        for (k = 1; k < 21; ++k) {
            map[i][k] += map[i][k - 1];
            map[i][k] %= 1000000000;
        }

    }

////显示数组
//    for (i = 0; i < 10; ++i) {
//        cout << i << " : ";
//        for (j = 0; j < 10; ++j) {
//            cout << map[i][j] << "\t";
//        }
//        cout << endl;
//    }
    cin >> T;
    while (T--) {
        cin >> N;
        cout << map[N][20] << endl;
    }
    return 0;
}