不知道为什么可以想到设 \(n_c\) 为颜色 \(c\) 的出现次数，那么 \(\prod n_c\) 也即选的方案数 \(\approx 1.25 \times 10^{11}\)。
发现 \(B = \sqrt{\prod n_c}\) 不大，考虑 meet-in-the-middle，把所有颜色分成两部分，每一部分的 \(\prod n_c\) 都接近 \(B\)。先搜出每一部分的所有可能的异或和，问题转化为，给定两个数组 \(a_{1 \sim n}\) 和 \(b_{1 \sim m}\)，求 \(a_i \oplus b_j\) 的第 \(k\) 大。
朴素想法是二分，二分后即求 \(a_i \oplus b_j \ge x\) 的对数。对 \(a\) 建 01Trie，对于每个 \(b_j\) 钦定到哪一位之前全部相等，在这一位异或起来 \(> x\)，在 Trie 上走一遍即可求得。但是时间复杂度是 \(O(B \log^2 V)\) 的，比较难通过。
必须得降一个 \(\log\)。考虑直接逐位确定答案，所有 \(b_i\) 同时在 Trie 树上走，对于每个 \(b_i\) 都维护一个 \(p_i\) 表示它当前的位置。那如果我们要判断当前位是否为 \(1\)，就把所有 \(p_i\) 往异于 \(b_i\) 当前位的方向走，累加子树大小，就是当前位为 \(1\) 的对数。时间复杂度降为 \(O(B \log V)\)，可以通过。
感觉技巧性挺强的。
code
// Problem: Ex - K-th beautiful Necklace
// Contest: AtCoder - AtCoder Beginner Contest 252
// URL: https://atcoder.jp/contests/abc252/tasks/abc252_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 75;
ll n, m, K, a[maxn], b[maxn];
int ch[40000000][2], ntot, sz[40000000], p[40000000];
vector<ll> vc[maxn], va, vb;
void dfs(int d, ll s, vector<ll> &v) {
if (d > m) {
v.pb(s);
return;
}
for (ll x : vc[d]) {
dfs(d + 2, s ^ x, v);
}
}
inline void insert(ll x) {
int p = 0;
for (int i = 59; ~i; --i) {
int t = ((x >> i) & 1);
if (!ch[p][t]) {
ch[p][t] = ++ntot;
}
p = ch[p][t];
++sz[p];
}
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &K);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i], &b[i]);
vc[a[i]].pb(b[i]);
}
if (m == 1) {
sort(b + 1, b + n + 1, greater<ll>());
printf("%lld\n", b[K]);
return;
}
sort(vc + 1, vc + m + 1, [&](auto a, auto b) {
return a.size() > b.size();
});
dfs(1, 0, va);
dfs(2, 0, vb);
for (ll x : vb) {
insert(x);
}
int t = (int)va.size();
ll ans = 0;
for (int d = 59; ~d; --d) {
ll s = 0;
for (int i = 0; i < t; ++i) {
if (p[i] == -1) {
continue;
}
s += sz[ch[p[i]][((va[i] >> d) & 1) ^ 1]];
}
bool fl = 0;
if (s < K) {
K -= s;
} else {
fl = 1;
ans |= (1LL << d);
}
for (int i = 0; i < t; ++i) {
if (p[i] == -1) {
continue;
}
p[i] = ch[p[i]][((va[i] >> d) & 1) ^ fl];
if (!p[i]) {
p[i] = -1;
}
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}