===
Index
简介与模板
异或线性基：用于处理多个数中选取一些数的XOR的最大值，最小值，第k大值，并可以查询能否通过集合中任意个数XOR得到，时间复杂度 O(n*log(n))。
线性基具有如下性质：
- 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
- 线性基是满足性质 1 的最小的集合。
- 线性基没有异或和为 0 的子集。
- 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
- 线性基中每个元素的二进制最高位互不相同。
线性基模板
struct xor_basis {
long long b[63], nb[63], tot;
xor_basis() : tot(0) {
memset(b, 0, sizeof(b));
memset(nb, 0, sizeof(nb));
}
// 向线性基中插入一个数
bool add(long long x) {
for(int i = 62; ~i; i--)
if (x & (1LL << i)) {
if (!b[i]) {b[i] = x; break;}
x ^= b[i];
}
return x > 0;
}
// 判断线性基中元素能否异或得到 x
bool check(long long x) {
for (int i = 63; ~i; --i)
if (x & (1LL << i)) {
if (!b[i]) return false;
x ^= b[i];
}
return 1;
}
//求线性空间与x异或的最大值
long long max_val(long long x = 0) {
long long res = x;
for(int i = 62; i >= 0; i--)
res = max(res, res ^ b[i]);
return res;
}
//求线性空间与x异或的最小值
long long min_val(long long x) {
long long res = x;
for(int i = 0;i <= 62; i++)
if (b[i]) res ^= b[i];
return res;
}
//将线性基改造成每一位相互独立，即对于二进制的某一位i，只有pi的这一位是1，其它都是0
void rebuild() {
tot = 0;
for(int i = 62; ~i; i--)
for(int j = i - 1; ~j; j--)
if (b[i] & (1LL << j)) b[i] ^= b[j];
for(int i = 0;i <= 62; i++)
if (b[i]) nb[tot++] = b[i];
}
//求线性基能够组成的数中的第K小
long long kth_min(long long k) {
if(k >= (1ll << tot)) return -1; //k大于子集总数, 找不到
long long res = 0;
for(int i = 62; i >= 0; i--)
if (k & (1LL << i)) res ^= nb[i];
return res;
}
};
线性基模板题
给定 n 个整数（可能重复），求在这些数中选取任意个，使得他们的异或和最大。
- 1 <= n <= 50
- 0 <= s[i] < 2e50
#include <bits/stdc++.h>
using namespace std;
struct xor_basis {
// ...
};
int main(){
int n;
cin >> n;
xor_basis b;
for (int i = 0; i < n; ++i) {
long long x;
cin >> x;
b.add(x);
}
cout << b.max_val() << "\n";
}
xor异或
有n个整数，q个询问，对于任意的x,y，能否将x与这n个数中的任意多个数异或任意多次后变为y。
- 1 <= n, q <= 1e5
- 保证所有运算均在int范围内
分析
x 与 这些数中任意多个数异或等于 y， 也就是这任意多个数异或和为 x^y， 该问题转化为这些元素的任意子集能否异或得到 x^y
#include <bits/stdc++.h>
using namespace std;
struct xor_basis {
// ...
};
int main(){
int n, q;
cin >> n;
xor_basis b;
for (int i = 0; i < n; ++i) {
long long x;
cin >> x;
b.add(x);
}
cin >> q;
while(q--) {
int x, y;
cin >> x >> y;
if (b.check(x ^ y)) cout<<"YES\n";
else cout<<"NO\n";
}
}
异或值第k小
给定n个数，q次查询，每次询问第k小的异或值。
分析
线性基模板题，注意0是否可取，如果tot==n，说明每个数对线性基都有贡献，则不可能取到0，直接输出第k小即可，否则要算上0。
#include <bits/stdc++.h>
using namespace std;
struct xor_basis {
// ...
};
int main() {
int t, n, q;
cin >> t;
while (t--) {
cin >> n;
xor_basis b;
for (int i=0;i<n;++i){
long long x;
cin >> x;
b.add(x)
}
cin >> q;
b.rebuild(); // 查询第k小前需要先rebuild
while (q--) {
long long k;
cin >> k;
if(b.tot !=n){
if(k == 1){
cout<<"0\n";
}else{
cout<<b.kth_min(k-1)<<"\n";
}
}else cout<<b.kth_min(k)<<"\n";
}
}
}
线性基的基底数目
有n个数，两个人轮流操作，每次操作，选一个数加入集合中， 如果在某次操作结束后，集合中存在一个异或和为0的非空子集，那么进行这次操作的人输，如果全部取完，则最后操作的人赢 问是先手必胜还是后手必胜。
- 1 <= n <= 1e5
- a[i] <= 2e61
分析
线性基有一个结论：线性基集合中的任何子集的异或和都不会为0。于是问题转化为，求该组数的线性基的基底有多少个。（一组数的线性基的基底个数是一定的）。如果是奇数那么是先手赢，否则是后手赢。
#include <bits/stdc++.h>
using namespace std;
struct xor_basis {
// ...
};
int main(){
xor_basis b;
int n, c = 0;
cin >> n;
long long x;
for (int i = 0; i < n; ++i) {
cin >> x;
if(b.add(x)) c++;
}
if(c%2==1) cout<<"First";
else cout<<"Second";
}
或者
// ...
int main(){
xor_basis b;
int n;
cin >> n;
long long x;
for (int i = 0; i < n; ++i) {
cin >> x;
b.add(x)
}
b.rebuild();
if(b.tot%2==1) cout<<"First";
else cout<<"Second";
}
