线性基
<pre><code class="language-cpp">#include <iostream>
using namespace std;
typedef long long ll;
bool zero = false;
ll xorbase[64], rxorbase[64];
int cnt = 0;
bool insert(ll x){
for(int i = 62; i >= 0; i--){
if(x & (1ll << i)){
if(xorbase[i]) x ^= xorbase[i];
else{
xorbase[i] = x;
return true;
break;
}
}
}
zero = true;
return false;
}
void build(){
for(int i = 62; i >= 0; i--){
for(int j = i-1; j >= 0; j--){
if(xorbase[i] & (1ll << j)){
xorbase[i] ^= xorbase[j];
}
}
}
for(ll i = 0; i <= 62; i++){
if (xorbase[i]) rxorbase[cnt++] = xorbase[i];
}
}
ll getKXor(ll k){
ll ans = 0;
for(int i = 62; i >= 0; i--){
if((1ll << i) & k) ans ^= rxorbase[i];
}
return ans;
}</code></pre>