代码

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

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define rsz resize
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define bit(k) (1 << (k))
#define Bit(k) (1ll << (k))
#define BIT(k) ((LL)1 << (k))
#define lowbit(x) ((x) & -(x))
#define bin(s, k) ((s) >> (k) & 1)
#define lg2(x) (31 - __builtin_clz(x))
#define LG2(x) (63 - __builtin_clzll(x))
#define popcnt(x) __builtin_popcount(x)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

// #define FILERR

#ifdef JYR
#ifdef FILERR
auto filerr = fopen("Test.err", "w");
#else
auto filerr = stderr;
#endif
#define errs(x) fputs(x "\n", filerr)
#define errm(x, ...) fprintf(filerr, x, ##__VA_ARGS__)
#else
#define errs(x) 0
#define errm(x, ...) 0
#endif

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_b < _a) _a = _b; }
template<typename T> T sq(T x) { return x * x; }

bool Mbe;

struct FastIO {
    char buf[1 << 20], *p1, *p2;
    char puf[1 << 20], *pf;

    FastIO() : p1(buf), p2(buf), pf(puf) {}
    ~FastIO() { fwrite(puf, 1, pf - puf, stdout); }

    char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin);
        return p1 == p2 ? EOF : *p1++;
    }

    bool blank(char c) { return c == ' ' || c == '\r' || c == '\n' || c == '\t'; }

    char rd() {
        char c = gc(); while (blank(c)) c = gc();
        return c;
    }

    template<typename T> T rd() {
        T x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        return f ? -x : x;
    }

    int rds(char *s) {
        char c = gc(), *S = s;
        while (blank(c)) c = gc();
        if (c == EOF) return *s = 0;
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }

    int rdl(char *s) {
        char c = gc(), *S = s;
        while (c == '\r' || c == '\n') c = gc();
        if (c == EOF) return *s = 0;
        while (c != '\r' && c != '\n' && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }

    void rd(char &c) { c = rd(); }

    void rd(char *s) {
        char c = gc();
        while (blank(c)) c = gc();
        if (c == EOF) { *s = 0; return; }
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        *s = 0;
    }

    template<typename T> void rd(T &x) {
        x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        if (f) x = -x;
    }

    template<typename T, typename... Ts>
    void rd(T& x, Ts&... xs) { rd(x), rd(xs...); }

    void pc(const char &c) {
        if (pf - puf == 1 << 20) fwrite(pf = puf, 1, 1 << 20, stdout);
        *pf++ = c;
    }

    void prt(char c) { pc(c); }
    void prt(char* s) { while (*s) pc(*s++); }
    void prt(const char* s) { while (*s) pc(*s++); }

    template<typename T> void prt(T x) {
        static int st[41], tp = 0;
        if (x == 0) { pc('0'); return; }
        if (x < 0) x = -x, pc('-');
        while (x) st[++tp] = x % 10, x /= 10;
        while (tp) pc(st[tp--] + '0');
    }

    template<typename T> void prt(T *x) { while (*x) pc(*x++); }

    template<typename T, typename... Ts>
    void prt(T x, Ts... xs) { prt(x), prt(xs...); }

    void prts(const char *s, char c = '\n') {
        while (*s) pc(*s++);
        if (c) pc(c);
    }
} IO;

#define rd IO.rd
#define rds IO.rds
#define ri rd<int>()
#define rl rd<ll>()
#define prt IO.prt
#define prs IO.prts
#define edl IO.pc('\n')

// #define MC

#define N 41
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

struct node {
    int c;
    ll s;
    ll S;
    node(ll _S = 0, int _c = inf, ll _s = 0) : S(_S), c(_c), s(_s) {}
};
bool operator<(const node &a, const node &b) { return a.S != b.S ? a.S < b.S : a.c < b.c; }
node& operator+=(node &a, const node &b) { return a.s += b.s, a; }
vector<node> f, g;

int n;
int a[N] = {0, 32, 16, 8, 40, 24, 4, 36, 20, 12, 28, 2, 34, 18, 10, 26, 6, 38, 22, 14, 30, 1, 33, 17, 9, 25, 5, 37, 21, 13, 29, 3, 35, 19, 11, 27, 7, 39, 23, 15, 31};
// int a[N];
ll su[N];
pair<int, ll> ans[N];

void mslv() {
    // rd(n), f.rsz(2);
    // rep(i, 1, n) a[i] = ri - 1;
    n = 40, f.rsz(2);
    rep(i, 1, n) a[i]--;
    f[0] = node((Bit(n) - 1) ^ Bit(a[1]), 0, 1);
    f[1] = node(Bit(n) - 1, 0, 1);
    per(i, n, 1) su[i] = su[i + 1] | Bit(a[i]);
    ll c, p, d, t, k, r, e, w;
    rep(i, 2, n) {
        c = (w = su[i + 1]) & ((r = Bit(e = a[i])) - 1);
        c = ~(!c ? 0 : Bit(LG2(c) + 1) - 1), w = ~w;
        c &= k = (r << 1) - 1, k = ~k;
        req(_, 0, f.size()) {
            auto &[cc, ss, s] = f[_];
            p = s & c;
            d = __builtin_ctzll((s & k) | Bit(n));
            t = p << (d - e - 1);
            g.eb(s ^ p ^ t, cc + __builtin_popcountll(s & k & w), ss);
            t = (p = (s ^= r) & c) << (d - e);
            g.eb(s ^ p ^ t, cc, ss);
        }
        sort(all(g)), f.rsz(1), f[0] = g[0];
        req(j, 1, g.size()) if (f.back().S == g[j].S) {
            auto &[vc, vs, S] = f.back();
            auto &[uc, us, _] = g[j];
            if (uc < vc) vc = uc, vs = us;
            else if (vc == uc) vs += us;
        } else f.eb(g[j]);
        g.clear();
    }
    rep(i, 1, n) ans[i].fi = inf;
    for (auto &[uc, us, S] : f) {
        auto &[vc, vs] = ans[__builtin_popcountll(S)];
        if (uc < vc) vc = uc, vs = us;
        else if (vc == uc) vs += us;
    }
    rep(i, 1, n) prt(ans[i].fi, ' ', ans[i].se, '\n');
}

void mprw() {}

bool Med;

int main() {
    #ifdef JYR
    errs("Running!");
    freopen("Test.in", "r", stdin);
    freopen("Test.out", "w", stdout);
    #endif
    mprw();
    #ifdef MC
    int _ = ri;
    while (_--) mslv();
    #else
    mslv();
    #endif
    errm("%.3lfMB %.0lfms\n", abs(&Med - &Mbe) / 1048576., clock() * 1000. / CLOCKS_PER_SEC);
    return 0;
}

评测结果