- 贪心构造出向量组的线性基:
void insert(int x){for(int i=63;i>=0;i--){if(x&(1ll<<i)){if(p[i]) x^=p[i];else {p[i]^=x;cnt++;break;}}}
}
贪心地选取每一位,如果这一位已经有了,就把它异或掉,可以证明到最后一定是一组基。
这样构造出来的线性基, p [ i ] p[i] p[i] 一定是表示首位为 1 1 1 的基,而且不会重复,插入单个元素复杂度 O ( l o g n ) O(logn) O(logn)。 - 寻找最大数:
int askmx(){int x=0;for(int i=63;i>=0;i--){if((x^p[i])>x) x^=p[i];}return x;
}
从高位到低位枚举,贪心选取最高位一定是对的。 - 寻找最小数:
int askmn(){int mn=inf;if(cnt==0||n>cnt) return 0;else{for(int i=0;i<=64;i++){if(p[i]) mn=min(mn,p[i]);}return mn;}}
一般来说,最小值就是贪心构造出来的线性基的某个值,但是需要考虑一个特殊情况——几个数异或起来变成了 0 0 0。这种情况只需要判断插入的数字的数量和这些数字构造出的基的数量,如果有数字没有成为基,那么它一定可以被其它基线性表出,这种情况会异或出0。 - 查询是否可以构造出某个数:
bool ask(int x){for(int i=63;i>=0;i--){if(x&(1ll<<i)){if(p[i]) x^=p[i];}}return (x==0);
}
从大到小异或,这样如果最后异或为 0 0 0,代表可以线性表出,不为零代表不行。 - 求第 k k k 大数:
void rebuild() {cnt=0;for(int i=63;i>=0;i--)for(int j=i-1;j>=0;j--)if(p[i]&(1LL<<j)) p[i]^=p[j];for(int i=0;i<=63;i++) if(p[i]) d[cnt++]=p[i];
}
int kth(int k) {if(k>=(1LL<<cnt)) return -1;int ans=0;for(int i=63;i>=0;i--)if(k&(1LL<<i)) ans^=d[i];return ans;
}
原来的线性基不满足求第 k k k 大的要求,不满足行阶梯型,即不会有两个线性基共享其中一个的最高位,如 10110 10110 10110 和 00100 00100 00100 ,不是一组完美的线性基。需要通过高斯消元求阶梯形。
求完之后,可以直接贪心选取第k个数。
这里还需要判断 0 0 0 的情况,如果会凑出 0 0 0 ,查询位置要递推 1 1 1。for(int i=0;i<64;i++) p[i]=0;
int n;cin>>n;
for(int i=1;i<=n;i++){int x;cin>>x;insert(x);
}
rebuild();
int m;cin>>m;
if(n>cnt) zero=1;
for(int i=1;i<=m;i++){int q;cin>>q;if(n>cnt&&q==1) cout<<0<<endl;else cout<<kth(q-zero)<<endl;
}