数位dp失败。

PE912.cpp

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

const int N = 65;

LL F0[N][2][2][2]; Int F[3][N][2][2][2]; bool vis[N][2][2][2]; Int p2[N+1];
bool a[N]; int an;

LL f0(int k, bool b, bool x, bool y) {
    LL &z = F0[k][b][x][y];
    if (!z) {
        if (k < 0) z = 1;
        else {
            z += f0(k-1, b && a[k] == 0, 0, x);
            if ((!x || !y) && (!b || a[k] == 1)) z += f0(k-1, b, 1, x);
        }
    }
    return z;
}

Int f(int k, bool b, bool x, bool y) {
    Int &z0 = F[0][k][b][x][y], &z1 = F[1][k][b][x][y], &z2 = F[2][k][b][x][y];
    if (!vis[k][b][x][y]) {
        vis[k][b][x][y] = true;
        if (k < 0) {
            if (!x) return 0;
            z0 = z1 = z2 = 1;
        } else {
            bool b0 = b && a[k] == 0;
            f(k-1, b0, 0, x);
            Int &v0 = F[0][k-1][b0][0][x];
            Int &v1 = F[1][k-1][b0][0][x];
            Int &v2 = F[2][k-1][b0][0][x];
            z0 += v0;
            z1 += v1;
            z2 += v2;
            //z1 += p2[k] * v0 + v1;
            //z2 += sqr(p2[k]) + 2 * p2[k]
            if ((!x || !y) && (!b || a[k] == 1)) {
                f(k-1, b, 1, x);
                Int &v0 = F[0][k-1][b][1][x];
                Int &v1 = F[1][k-1][b][1][x];
                Int &v2 = F[2][k-1][b][1][x];
                z0 += v0;
                z1 += p2[k] * v0 + v1;
                z2 += sqr(p2[k]) * v0  + p2[k+1] * v1 + v2;
            }
        }
    }
    return z2;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    //cout << MOD << endl;
    uLL l = 1, r = 2e18;
    while (l < r) {
        RST(F0); uLL n = (l + r) / 2, m = n; an = 0; while (n) {
            a[an++] = n & 1;
            n >>= 1;
        }
        LL c = f0(an-1, 1, 0, 0) - 1;
        //cout << l << " " << r << " " << m << " " << c << endl;
        if (c < uLL(10)) l = m + 1;
        else r = m;
    }
    cout << l << " " << r << endl;

    // 1 2 3 4 5 6 8 9 10 11
    // 1 4 9 16 25 36 64 81 100 121

     uLL n = l; an = 0; while (n) {
        a[an++] = n & 1;
        n >>= 1;
    }
    p2[0] = 1; FOR(i, 1, an) p2[i] = p2[i] * 2;

    cout << f(an-1, 1, 0, 0) << endl;



}