7-6 整数拆分 （15 分）
Jack Cheng学完了计算机基础导论，了解到任何一个数都可以用二进制数来表示，爱玩游戏的他忍不住想要玩一个游戏，既然可以用二进制数表示，那么就可以写成若干个二进制数相加，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2、7=1+1+1+1+1+2 ，7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。 用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。现在他希望你和他一起来玩这个游戏。

输入格式:
请在这里写输入格式。例如：输入在一行中给出2个绝对值不超过1000的整数A和B。

输出格式:
第一行输入n表示有那个输入，后面每一行输入一个N(1<=N<=1000000)。所有输出只占一行（行末无多余空格）。

输入样例:
1
7
输出样例:
6

对于一个奇数来说，其拆分的情况是等同于比它小1的偶数的
对于一个偶数来说,其拆分情况是 f[i] = f[i-1]+f[i/2];

因为只能用”二进制数“表示，即二进制形式中只能有一个1，所以所有奇数最后的那个1，只能由1进行构成，所以其拆分的情况是等同于比它小1的偶数的拆分数。

对于偶数来说的计算方法暂时还没搞懂，姑且先记录一下。

#include<bits/stdc++.h> 
using namespace std;

#define ll long long
const ll maxn = 1e6+5;
const double pi = acos(-1.0);
const ll inf = 0x3f3f3f3f;
const ll mod = 1000000000;

ll pre[maxn];
void init() {
    pre[1] = 1; 
    
    for(ll i = 2; i <= 1000000; i++){
        if (i % 2) pre[i] = pre[i-1];
        else pre[i] = pre[i-1] + pre[i/2];
        pre[i] %= mod;
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    ll t, n;
    
    cin >> t;
    init();
    while(t--){
        cin >> n;
         printf("%lld%c", pre[n], t==0?'\n':' ');
    }
    return 0;
}