发现 \(O(2^w)\) 过不了但是 \(O(2^{\frac{w}{2}})\) 过得了(\(w\) 为数二进制形式位数,此题为 \(30\)),且异或操作表明每一位之间不会互相影响,很明显上个折半搜索就行。
考虑怎么合并,和 CF585D 同样的套路,考虑前半部分得到的为 \(c_{1\sim n}\),后半部分为 \(c'_{1\sim n}\),则有 \(c_1 + c'_1 = c_2 + c'_2 =\cdots = c_n + c'_n\)。
然后把 \(c\) 放到一边,\(c'\) 放到另一边就有 \(c_1 - c_2 = c'_2 - c'_1, \cdots,c_1 - c_n = c'_n - c'_1\),于是用后半部分的 \((c'_2 - c'_1,\cdots,c'_n - c'_1)\) 查找前半部分的 \((c_1 - c_2,\cdots,c_n - c_1)\) 即可。
时间复杂度 \(O(2^{\frac{n}{2}}\log_2 2^{\frac{n}{2}})\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: F. Make Them Similar
// Contest: Codeforces - Educational Codeforces Round 76 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1257/problem/F
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, M = 30;
int n;
int a[N][M], cnt[N];
map<basic_string<int>, int> mp;
void dfs1(int w, int s) {
if (w >= M / 2) {
basic_string<int> u;
for (int i = 2; i <= n; i++) {
u += cnt[1] - cnt[i];
}
mp[u] = s;
return ;
}
for (int i = 1; i <= n; i++) {
cnt[i] += a[i][w];
}
dfs1(w + 1, s);
for (int i = 1; i <= n; i++) {
cnt[i] -= a[i][w];
}
for (int i = 1; i <= n; i++) {
cnt[i] += 1 - a[i][w];
}
dfs1(w + 1, s + (1 << w));
for (int i = 1; i <= n; i++) {
cnt[i] -= 1 - a[i][w];
}
return ;
}
void dfs2(int w, int s) {
if (w >= M) {
basic_string<int> u;
for (int i = 2; i <= n; i++) {
u += cnt[i] - cnt[1];
}
if (mp.count(u)) {
printf("%d", s + mp[u]);
exit(0);
}
return ;
}
for (int i = 1; i <= n; i++) {
cnt[i] += a[i][w];
}
dfs2(w + 1, s);
for (int i = 1; i <= n; i++) {
cnt[i] -= a[i][w];
}
for (int i = 1; i <= n; i++) {
cnt[i] += 1 - a[i][w];
}
dfs2(w + 1, s + (1 << w));
for (int i = 1; i <= n; i++) {
cnt[i] -= 1 - a[i][w];
}
return ;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
for (int j = 0; j < M; j++, x >>= 1) {
a[i][j] = x & 1;
}
}
dfs1(0, 0);
dfs2(M / 2, 0);
printf("-1");
return 0;
}