#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 101;
int T, n, m, q;
ll K;
int cnt = 0;
struct LinearBasis{
ll a[maxn + 10];
int b[maxn];
int insert(ll t){
for(int j = 62 ; j >= 0 ; --j){
if(!t) return 0;
if(t & (1ll << j)){
if(a[j]){
t = t ^ a[j];
} else{
for(int k = 0 ; k < j ; ++k){
if(t & (1ll << k)) t = t ^ a[k];
}
for(int k = j + 1 ; k <= 62 ; ++k){
if(a[k] & (1ll << j)) a[k] = a[k] ^ t;
}
a[j] = t;
return 1;
}
}
}
return 0;
}
}A;
bool check(ll k){
ll ans = 0;
for(int i = 0 ; i <= 62 ; ++i){
if((k >> i) & 1){
ans ^= A.a[i];
}
}
return ans > K;
// }
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
// freopen("data.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(), K = read();
ll x;
for(int i = 1 ; i <= n ; ++i){
x = read();
cnt += A.insert(x);
}
for (int i = 0, j = 0; i <= 62; ++i)
if (A.a[i])
A.a[j++] = A.a[i];
ll l = 0, r = (1 << cnt) - 1;
while(l < r){
ll mid = (l + r + 1) >> 1;
if(check(mid)){
r = mid - 1;
} else{
l = mid;
}
}
// printf("%lld\n", r);
cout << (1 << cnt) - l - 1;
return 0;
}
全部评论
(1) 回帖