线性基笔记

本人蒟蒻，如有错误还请指出

打牛客时盯了一题两个小时毫无头绪一头雾水，一看题解线性基人麻了，于是就有了这篇文章...

线性基的概念

首先，线性基是什么？有什么用？

线性基是一个数的集合，取线性基中若干个数异或起来可以得到原序列中的任意一个数。

线性基的构造

其构造方法为：

从最高位往低位枚举，用表示为线性基中最高位为的数，当一个数二进制下第位为1时，如果不存在就对赋值，否则将这个数异或上。如果这个数中途被异或成0了，那么说明这个数可以被线性基中的一些数异或得到，则不需要将这个数插到线性基中。

具体则表示为这样：

代码则表示为：

void insert(int x) { for (int i = 60; i >= 0; i--) if ((x >> i) & 1) { if (!d[i]) { d[i] = x; return; } x ^= d[i]; } zero = 1; }

注：此处zero用于记录是否有元素无法插入到线性基中，在下文求异或最小值处提到。

线性基的性质

性质一

原序列中的任意一个数都可以通过线性基中的若干个数异或表示。

因为如果无法表示，那么他必然可以加到线性基中。

性质二

线性基中任意数异或起来不可能为0。

假设^^=0，则^=，可以由^表示，由性质一可知，无法被插到线性基中。

性质三

在满足性质一条件下，线性基中的数的个数最少。

如果我们多插入了一个数x，而x又可以由原线性基中的一些数异或得到，那么这个数显然是多余的。

线性基的作用

求异或最大值

求异或最大值本质上是一个贪心的过程。

从最高位往低位枚举，如果该位线性基存在，并且异或后结果变大，则异或上该位的线性基。

int qmax() { int res = 0; for (int i = 60; i >= 0; i--) if ((res ^ d[i]) > res) res ^= d[i]; return res; }

求异或最小值

由性质二可知线性基无法表示0，因此我们要分类讨论。

如果一个数无法被插入到线性基中，则说明他可以被线性基中的元素表示，即存在一些数的异或值为0，这一点只需要用一个变量zero在插入的时候记录一下是否变成0，即无法插入到线性基中即可。

如果不存在0异或的异或值，那么最小的线性基就是答案，因为最小的线性基最高位最小，值最小。

int qmin() { if (zero) return 0; for (int i = 0; i <= 60; i++) if (d[i]) return d[i]; return 0; }

求第k小的异或值

由于线性基无法存0，因此当存在0时，k要先减1。

我们要先对线性基做一个处理，对于每一位，从到枚举每一位，如果存在并且的第位为1，那么让的异或上。处理完后，线性基中的数应该长这样：

最后再把新的线性基的数加到新数组p中，接下来找第k小的值时，只需要将k二进制拆分，如果k的第位为1，就异或上。注意，不是异或上原线性基中元素。

int query(int k) { k -= zero; if (!k) return 0; for (int i = 60; i >= 0; i--) for (int j = i - 1; j >= 0; j--) if (d[i] & (1LL << j)) d[i] ^= d[j]; for (int i = 0; i <= 60; i++) if (d[i]) p[cnt++] = d[i]; if (k >= (1LL << cnt)) return -1; int res = 0; for (int i = 0; i < cnt; i++) if ((k >> i) & 1) res ^= p[i]; return res; }

判断一个数是否能被线性基中的一些数异或得到

只需要尝试将这个数插入到线性基中，如果这个数最后变成0了，即这个数不能插入到线性基中，说明这个数可以被线性基中的一些数异或得到，否则不能。

int check(int x) { for (int i = 60; i >= 0; i--) { if ((x >> i) & 1) x ^= d[i]; if (x == 0) return 1; } return 0; }

查询一个数可以由原序列中的哪些数异或得到

线性基一个非常强大的作用是可以直接找出一个数由原序列中的哪些数异或得到。

这一步查询本质上是一个哈希的过程。在线性基中插入元素时，我们可以同时存储这一位的哈希值，当一个数由这一位异或而来时，我们只需要异或上这一位的哈希值。最后再对这个哈希值做一个解码。这样我们就可以找到由哪些数异或而来了。

bool insert(int val, int idx) { ull cul = 0; for (int i = 30; i >= 0; i--) if ((val >> i) & 1) { if (!d[i]) { d[i] = val; mask[i] = cul | (1ull << rep.size()); rep.push_back(idx); return true; } val ^= d[i]; cul ^= mask[i]; } zero = 1; return false; } pair<bool, ull> check(int val) { ull res = 0; for (int i = 30; i >= 0; i--) { if ((val >> i) & 1) { if (!d[i]) return {false, 0}; val ^= d[i]; res ^= mask[i]; } } return {true, res}; } vector<int> choose(ull msk) { vector<int> res; for (int i = 0; i < rep.size(); i++) if ((msk >> i) & 1) res.push_back(rep[i]); return res; }

模板

int zero = 0, cnt = 0; int d[61], p[61]; ull mask[61]; vector<int> rep; bool insert(int val, int idx) { ull cul = 0; for (int i = 30; i >= 0; i--) if ((val >> i) & 1) { if (!d[i]) { d[i] = val; mask[i] = cul | (1ull << rep.size()); rep.push_back(idx); return true; } val ^= d[i]; cul ^= mask[i]; } zero = 1; return false; } int qmax() { int res = 0; for (int i = 30; i >= 0; i--) if ((res ^ d[i]) > res) res ^= d[i]; return res; } int qmin() { if (zero) return 0; for (int i = 0; i <= 30; i++) if (d[i]) return d[i]; return 0; } void rebuild() { for (int i = 30; i >= 0; i--) for (int j = i - 1; j >= 0; j--) if (d[i] & (1LL << j)) d[i] ^= d[j]; for (int i = 0; i <= 30; i++) if (d[i]) p[cnt++] = d[i]; } int query(int k) { k -= zero; if (!k) return 0; rebuild(); if (k >= (1LL << cnt)) return -1; int res = 0; for (int i = 0; i < cnt; i++) if ((k >> i) & 1) res ^= p[i]; return res; } pair<bool, ull> check(int val) { ull res = 0; for (int i = 30; i >= 0; i--) { if ((val >> i) & 1) { if (!d[i]) return {false, 0}; val ^= d[i]; res ^= mask[i]; } } return {true, res}; } vector<int> choose(ull msk) { vector<int> res; for (int i = 0; i < rep.size(); i++) if ((msk >> i) & 1) res.push_back(rep[i]); return res; } void clear() { for (int i = 0; i <= 30; i++) d[i] = p[i] = mask[i] = 0; cnt = 0; zero = 0; rep.clear(); }

题目

原题链接

回到这道我两个小时没有任何头绪的题

我去，这不一眼秒？

题目大意

有两个长度为n的数组和，构造一个数组等于或者，使得^^...^等于0

思路

先让等于，如果异或结果已经为0，那么答案就为数组，如果要让替换成，那就异或上^。也就是说，令原先数组的异或结果为，如果为0答案就为数组，否则，就要异或上若干个^使得最后的结果为0。那么只需要找出一些^的位置使得异或结果为即可。

代码

void solve() { clear(); cin >> n; int t = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; t ^= a[i]; st[i] = 0; } for (int i = 1; i <= n; i++) { cin >> b[i]; if ((a[i] ^ b[i]) == 0) continue; insert(a[i] ^ b[i], i); } if (t == 0) { for (int i = 1; i <= n; i++) cout << a[i] << ' '; cout << endl; return; } auto [flag, msk] = check(t); if (!flag) { cout << -1 << endl; return; } vector<int> ans = choose(msk); for (int x : ans) st[x] = 1; for (int i = 1; i <= n; i++) if (st[i]) cout << b[i] << ' '; else cout << a[i] << ' '; cout << endl; }

参考文献

线性基详解

题解