打表找规律 + 递归，高精度是多余的。。。

PE918.cpp

#include <lastweapon/number>
#include <lastweapon/bitwise>
#include <lastweapon/bignum>
using namespace lastweapon;

const int N = 112;


class bignum2 : bignum {
public:
    bignum t;
    bool s = 1;

    bignum2() {
        t = 0;
        s = 1;
    }
    bignum2(bignum tt) {
        t = tt;
        s = 1;
    }

    bignum2 operator +(const bignum2 r) {
        bignum2 l = *this;
        if (r.s == s) {
            l.t += r.t;
        } else {
            if (l.t >= r.t) {
                l.t -= r.t;
            } else {
                l.s = r.s;
                l.t = r.t - l.t;
            }
        }
        return l;
    }
    bignum2 operator -(const bignum2 r) {
        bignum2 rr = r;
        rr.s ^= 1;
        return (*this) + rr;
    }

    friend ostream& operator<<(ostream&, const bignum2&);
};

inline ostream& operator<<(ostream& output, const bignum2& a){
    if (a.s == 0) output << "-";
    output << a.t;
}


LL a[N], s[N];

//
// 1 3
// 2 6
// 4 12

map<LL,LL> A;

LL aa(LL n) {
    if (!CTN(A, n)) {
        if (n&1) {
            A[n] = aa(n/2) - aa(n/2+1)-aa(n/2+1)-aa(n/2+1);
        } else {
            A[n] = aa(n/2)+aa(n/2);
        }
    }
    return A[n];
}

LL S(LL n, LL lv = 0) {
    cout << n << endl;
    //return 0;
    //
    if (n == 0) return 0;

    LL z = 0; LL b = 1LL<<(lv+1);
    if (n >= 1) {
        //z += a[b/2];
        //cout << b/2 << endl;
        z = z + aa(b/2);
    }
    if (n >= 3) {
        //z += a[b/2 + b];
        //cout << b/2+b << endl;
        z = z + aa(b/2 + b);
    }
    if (n >= 5 && n%4 < 3 && n%4 > 0) {
        //z += a[(n/4*4+1)<<lv];
        //cout << (n/4*4+1)<<lv<< endl;
        z = z + aa((n/4*4+1)<<lv);
    }
    //cout << z << endl;
    //cout << n << " " << lv << " " << z << endl;
    return z + S(n/2, lv+1);
}
// 0 1 2 3 4 5 6 7 8 9 10
//     -   -   -   -   -
//a[2]
//a[6]
//a[8]
//2 -10 8 = 0

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    a[1] = 1; s[1] = 1; A[1] = 1; A[0] = 0;
    //a[1] = a[1] - a[1] * 50;
    //cout << a[1] << endl;
    //return 0;
    //cout << a[1] - 3*10;
    //return 0;
    FOR(i, 2, N) {

        cout << i << endl;

        if (i&1) {
            a[i] = a[i/2] - a[i/2+1] - a[i/2+1] - a[i/2+1];
        } else {
            a[i] = a[i/2] + a[i/2];
        }

        A[i] = a[i];
        s[i] = s[i-1] + a[i];
        cout << i << " " << a[i] << " " << s[i] << endl;
        //if (count_bits(i-1) == 1)
        //cout << i << " " << -i/2+4 << " " << s[i] << endl;
          //  cout << s[i] - (-i/2+4 ) << endl;
        /*if (a[i] == -a[i-4]) {
            cout << i-4 << endl;
            cout << i << endl;
        }*/
    }


    //cout << endl;*/
    cout << "---------" << endl;
    cout << S(1000000000000) << endl;
    cout << aa(1001) << endl;
}
//              -5 -2  1

/*
2: 3
3: -2
4: 2
5: 19
6: 9
7: -8
8: 0
9: -47
10: -13
11: 34
12: 14
13: 55
14: 21
15: -20
16: -4
17: 145
18: 51
19: -98
20: -30
*/

//a[8]  = 2a[4]
//a[9]  = a[4]] - 3a[5]

//a[7] = 2a3a - 3a4

//3 -2 2 19 9 -8 0 -47 -13 34 14 55 21 -20 -4 145 51 -98 -30 -137 -43 64 24 -119 -37 106 38 127 45 -44 -12 -443 -145 286 98 451 153 -200 -64 325 111 -278 -90 -317 -103 124 44 433 147 -242 -78 -425 -139 208 72 -263 -85 250 86 271 93 -92 -28 1297 435 -890 -294 -1289 -427 568 192 -1055 -349 898 302 1063 357 -404 -132 -1163 -385 646 218 1171 393 -560 -184 685 231 -638 -210 -677 -223 244 84 -1163 -385 862 290 1171 393 -488 -160 1045 351 -854 -282 -1037 -343 412 140 1009 339 -530 -174 -1001 -331 496 168 -551 -181 538 182 559 189 -188 -60 -3971 -1321 2590 866 3979 1329 -1784 -592 2989 999 -2582 -858 -2981 -991 1132 380 3745 1251 -2114 -702 -3737 -1243 1792 600 -2279 -757 2122 710 2287 765 -812 -268 3097 1035 -2330 -774 -3089 -1027 1288 432 -2855 -949 2338 782 2863 957 -1124 -372 -2603 -865 1366 458 2611 873 -1280 -424 1405 471 -1358 -450 -1397 -463 484 164 3745 1251 -2330 -774 -3737 -1243 1720 576

//
// 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
//   x   x   x
//     x       x           x
//         x