[ABC252Ex] K-th beautiful Necklace

Petit_Souris · 2025-09-05 14:48:09 · 个人记录

退役老登诈尸，上号写个题解。

很显然状态数上界是 M = e^{n/e}，仔细一算发现居然不到 2\times 10^{11}，一下就想到 meet in the middle。

考虑随机打乱序列并取状态数乘积 <B 的前缀，并对两部分进行纯暴力搜索。这样问题就变成从两个序列中各选出一个数异或起来第 K 大。

显然可以在 trie 树上逐位二分。具体而言，对于 a, b 两个序列，a 建立 trie 树，并维护 b 序列每个数目前走到了哪个节点。按位贪心，如果当前位是 1 的方案数 \ge K 就走 1，否则走 0。注意如果节点编号从 0 开始可能会有意想不到的错误，需要刻意避免。

时间复杂度 \mathcal O(\sqrt M \log V)，可议通过。

::::info[Code]

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 75, T = 3e5, O = 4e7 + 9;
ll n, C, K, id[N], p[2][N], len[2];
mt19937 rnd(time(0));
Ve<ll> vec[N];
int ch[O][2], tot, sz[O];
ll seq[O], plen;
int pos[O];
void Ins(ll x) {
    ll u = 0;
    per(i, 59, 0) {
        ll v = (x >> i) & 1;
        if(!ch[u][v]) ch[u][v] = ++tot;
        u = ch[u][v], sz[u]++;
    }
}
void dfs(ll id, ll x, ll xsum) {
    if(x == len[id] + 1) {
        if(id == 0) Ins(xsum);
        else seq[++plen] = xsum;
        return ;
    }
    for(ll z : vec[p[id][x]]) dfs(id, x + 1, xsum ^ z);
}
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read(), C = read(), K = read();
    rep(i, 1, n) {
        ll x = read(), y = read();
        vec[x].pb(y);
    }
    iota(id + 1, id + n + 1, 1ll);
    ll Z = 1e5, bst = 0;
    while(Z--) {
        shuffle(id + 1, id + C + 1, rnd);
        ll prod = 1, pos = C;
        rep(i, 1, C) {
            if(prod * vec[id[i]].size() > T) {
                pos = i - 1;
                break;
            }
            prod *= vec[id[i]].size();
        }
        if(prod > bst) {
            len[0] = len[1] = 0;
            rep(i, 1, pos) p[0][++len[0]] = id[i];
            rep(i, pos + 1, C) p[1][++len[1]] = id[i];
            bst = prod;
        }
    }
    dfs(0, 1, 0), dfs(1, 1, 0);
    ll ans = 0;
    per(i, 59, 0) {
        ll cnt = 0;
        rep(j, 1, plen) {
            ll v = (seq[j] >> i) & 1;
            if(!~pos[j]) continue;
            ll npos = ch[pos[j]][v ^ 1];
            cnt += sz[npos];
        }
        if(cnt >= K) {
            ans |= (1ll << i);
            rep(j, 1, plen) {
                ll v = (seq[j] >> i) & 1;
                if(!~pos[j]) continue;
                pos[j] = ch[pos[j]][v ^ 1];
                if(!pos[j]) pos[j] = -1;
            }
        }
        else {
            K -= cnt;
            rep(j, 1, plen) {
                ll v = (seq[j] >> i) & 1;
                if(!~pos[j]) continue;
                pos[j] = ch[pos[j]][v];
                if(!pos[j]) pos[j] = -1;
            }
        }
    }
    write(ans), putchar('\n');
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

::::