Give me the answer （C++代码）

解题思路:

先按照题意码了代码，思路见链接：

https://blog.dotcpp.com/a/57074

然后发现内存爆了，只好改变一下思路。

输出前50个值，寻找规律，发现连续的两个值是一样的。

然后把数组改小，变成一半，依旧爆内存，，，

迷啊，，

再改，，

找规律，，

1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25
1   2   4   6   10  14  20  26  36  46  60  74  94  114 140 166 202 238 284 330 390 450 524 598 692

发现第i个值等于第i-1和第(i+1)/2个值相等。

注意事项:

将“/2”运算转化成“>>1”会提高运行速度

参考代码:

#include <iostream>

using namespace std;

int map[500002];

int main() {
    int T, N;
    map[0] = 0;
    map[1] = 1;
    for (int i = 2; i < 500002; ++i) {
        map[i] = (map[i - 1] + map[(i + 1) >> 1]) % 1000000000;
    }
    cin >> T;
    while (T--) {
        cin >> N;
        cout << map[(N >> 1) + 1] << endl;
    }
    return 0;
}

后记：

查了一下map[i] = map[i - 1] + map[(i + 1)/2]的原理和解释，，

将n用二进制表示. 
n=1,只有1种表示方法。 
n=2，10(2)，二进制表示下，可以分拆成{1,1}，{10}有两种表示方法 
n=3, 11(2),可以分拆成{1,1,1},{10,1}. 
n=4, 100(2),{1,1,1,1},{10,1,1},{10,10},{100}. 
总结：如果所求的n为奇数，那么所求的分解结果中必含有1， 
因此，直接将n-1的分拆结果中添加一个1即可 为s[n-1] 
如果所求的n为偶数，那么n的分解结果分两种情况 
1.含有1 这种情况可以直接在n-1的分解结果中添加一个1即可 s[n-1] 
2.不含有1 那么，分解因子的都是偶数，将每个分解的因子都除以2， 
刚好是n/2的分解结果，并且可以与之一一对应，这种情况有 s[n/2]

原文链接：https://www.cnblogs.com/playboy307/p/5273600.html