异或线性空间求第kth值
#include <bits/stdc++.h> using namespace std; #define QWQ main #define int long long #define endl '\n' typedef long long ll; typedef unsigned long long ull; const int N = 63; int p[N]; int n,sz=0,tot = 0; bool insert(int x){ for(int i=63;i>=0;i--){ if((x >> i) & 1){ if(!p[i]){ p[i] = x; return true; } x = x^p[i]; } } return false; } void prework(){ for(int i=63;i>=0;i--){ for(int j=i-1;j>=0;j--){ if(p[i]&(1LL<<j)){ p[i]^=p[j]; } } } } ll getkth(int k){ if(sz<n){ if(k==1)return 0; --k; } if(k>=(1LL<<sz))return -1; prework(); ll ans = 0; for(int i=0;i<=63;i++){ if(p[i]){ if(k&1)ans^=p[i]; k>>=1; } } return ans; } void __Raihrtmoli__() { memset(p,0,sizeof(p)); sz = 0; cin>>n; for(int i=0;i<n;i++){ int x;cin>>x; if(insert(x))++sz; } int m;cin>>m; for(int i=0;i<m;i++){ int k;cin>>k; cout<<getkth(k)<<endl; } } signed QWQ() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int T;cin>>T; for(int i=1;i<=T;i++){ cout<<"Case #"<<i<<":"<<endl; __Raihrtmoli__(); } }
