不知道为什么可以想到设 \(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\) 在 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;
}
- beautiful Beginner Necklace AtCoder Contestbeautiful beginner necklace atcoder contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315