Contents
性质
- 线性基的二进制最高位互不相同
- 原序列里面的任意一个数都可以由线性基里面的一些数异或得到
- 线性基里面的任意一些数异或起来都不能得到 0
- 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的
线性基的基本操作
最大化异或和
题目大意： 给 n 个数，最大化异或和
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
const int M = 62;
int n;
struct Linear_Base{
long long d[100]; int tot;
void init() {
tot = 0;
memset(d, 0, sizeof(d));
}
bool insert(long long x) {
for (int i = M; i >= 0; i--) {
if (!(x >> i)) continue;
if (!d[i]) {
d[i] = x; tot++; break;
}
x ^= d[i];
}
return x > 0;
}
long long qmax() {
long long ans = 0;
for (int i = M; i >= 0; i--) {
if ((ans ^ d[i]) > ans) ans ^= d[i];
}
return ans;
}
}LB;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
long long a; scanf("%lld", &a);
LB.insert(a);
}
printf("%lld\n", LB.qmax());
return 0;
}
其他操作
线性基还可以实现以下几个查询：
- 查询是否可以异或出某个数 x；
- 查询线性基可以异或出的最小值；
- 查询 x 是线性基中可以异或出的第几名；
- 查询线性基可以异或出的第 k 小值。
题目大意：
求线性基的第 k 小值。
解题思路：
首先判断给的 n 个数是否线性无关。如果线性相关（某个数插入线性基失败），说明可以异或出 0；
然后对线性基做高斯消元，从最小的线性基开始枚举即可。
#include <bits/stdc++.h>
using namespace std;
const int M = 62;
struct Linear_Base{
long long d[100]; int tot;
vector<long long> v;
bool zero;
void init() {
tot = zero = 0;
memset(d, 0, sizeof(d));
v.resize(0);
}
bool insert(long long x) {
for (int i = M; i >= 0; i--) {
if (!(x >> i)) continue;
if (!d[i]) {
d[i] = x; tot++; break;
}
x ^= d[i];
}
if (!zero && !x) zero = true;
return x > 0;
}
long long qmax() {
long long ans = 0;
for (int i = M; i >= 0; i--) {
if ((ans ^ d[i]) > ans) ans ^= d[i];
}
return ans;
}
long long qmin() {
if (zero) return 0;
for (int i = 0; i <= M; i++) {
if (d[i]) return d[i];
}
return 0;
}
bool count(long long x) {
for (int i = M; i >= 0; i--) {
if (x & (1LL << i)) x ^= d[i];
}
return !x;
}
long long rank(long long x) {
if (!count(x)) return -1;
for (int i = 0; i <= M; i++) {
if (d[i]) v.push_back(i);
}
int sz = (int)v.size(); long long ans = 0;
if (zero) ans++;
// 如果允许选择空集，则不需要 if 判断，直接 ans++
for (int i = 0; i < sz; i++) {
if ((x >> v[i]) & 1)
ans += (1LL << i);
}
return ans;
}
void rebuild() {
for (int i = M; i >= 0; i--) {
if (!d[i]) continue;
for (int j = i - 1; j >= 0; j--) {
if (!d[j]) continue;
if (d[i] & (1LL << j)) d[i] ^= d[j];
}
}
for (int i = 0; i <= M; i++) {
if (d[i]) v.push_back(d[i]);
}
}
long long kthMin(long long k) {
if (zero) k--;
int sz = (int)v.size(); long long ans = 0;
if (k >= (1LL << sz)) return -1;
for (int i = 0; i < sz; i++) {
if ((k >> i) & 1) {
ans ^= v[i];
}
}
return ans;
}
}LB;
int main(int argc, const char * argv[]) {
int T, n, q; scanf("%d", &T);
for (int kase = 1; kase <= T; kase++) {
LB.init();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
long long x; scanf("%lld", &x);
LB.insert(x);
}
LB.rebuild();
scanf("%d", &q);
printf("Case #%d:\n", kase);
for (int i = 1; i <= q; i++) {
long long k; scanf("%lld", &k);
printf("%lld\n", LB.kthMin(k));
}
}
return 0;
}
线性基的高级操作
前缀线性基
题目大意：
给定 n 和 a_{i\dots n}，有 q 个询问：给定 l,r，求在 a_{l\dots r} 中选取任意个，使得他们的异或和最大。
解题思路：
对每个前缀建立一个线性基。对于已有的线性基，新插入时把原先的给置换出去（保持每个位置的线性基为最新）。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 50;
const int M = 25;
struct Prifix_LB {
long long d[M + 5]; int pos[M + 5];
void insert(Prifix_LB &lst, int id, long long w) {
*this = lst;
for (int i = M; i >= 0; i--) {
if ((w >> i) & 1) {
if (!d[i]) {
d[i] = w; pos[i] = id; return;
}
else if (pos[i] < id) {
swap(id, pos[i]); swap(w, d[i]);
}
w ^= d[i];
}
}
}
long long query(long long l) {
long long ret = 0;
for (int i = M; i >= 0; i--) {
if (d[i] && pos[i] >= l) ret = max(ret, ret ^ d[i]);
}
return ret;
}
}LB[N];
int main(int argc, const char * argv[]) {
int n, q; scanf("%d", &n);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
LB[i].insert(LB[i - 1], i, x);
}
scanf("%d", &q);
for (int i = 1, l, r; i <= q; i++) {
scanf("%d%d", &l, &r);
printf("%lld\n", LB[r].query(l));
}
return 0;
}
最大异或和路径
题目大意：
给定一个 n(n\le 50000) 个点 m(m\le 10000) 条边的无向图，每条边上有一个权值。请你求一条从 1 到 n 的路径，使得路径上的边的异或和最大。
题目分析：
任意一条 1 到 n 的路径的异或和，都可以由任意一条 1 到 n 路径的异或和与图中的一些环的异或和来组合得到：如果路径和环不相交，连接环和路径的边会走两次抵消掉；如果相交，相交的部分计算两次被抵消掉，不相交的部分构成一条新的路径。
因此我们只需要维护一个所有环异或和构成的线性基。查询的时候，初始 ans 等于任意一条路径的异或和，而非 0。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 50;
const int M = 62;
int n, m;
int head[N], tot;
struct Edge {
int nex, to;
long long w;
}e[N];
void add(int a, int b, long long c) {
e[++tot] = (Edge) {head[a], b, c};
head[a] = tot;
}
struct Linear_Base{
long long d[100];
void insert(long long x) {
for (int i = M; i >= 0; i--) {
if (!(x >> i)) continue;
if (!d[i]) {
d[i] = x; break;
}
x ^= d[i];
}
}
long long qmax(long long x) {
long long ans = x;
for (int i = M; i >= 0; i--) {
if ((ans ^ d[i]) > ans) ans ^= d[i];
}
return ans;
}
}LB;
int vis[N]; long long x[N];
void dfs(int u, int fa, long long ret) {
vis[u] = 1; x[u] = ret;
for (int i = head[u]; i; i = e[i].nex) {
int to = e[i].to;
if (to == fa) continue;
if (!vis[to]) dfs(to, u, ret ^ e[i].w);
else LB.insert(x[to] ^ ret ^ e[i].w);
}
}
int main(int argc, const char * argv[]) {
scanf("%d%d", &n, &m);
for (int i = 1, a, b; i <= m; i++) {
long long c;
scanf("%d%d%lld", &a, &b, &c);
add(a, b, c); add(b, a, c);
}
dfs(1, 0, 0);
printf("%lld\n", LB.qmax(x[n]));
return 0;
}
异或方案数
题目链接：P4869 albus就是要第一个出场
题目大意：
A_{1\cdots n} 是一个序列，f(A)=A_1\oplus A_2\oplus\cdots\oplus A_n，f(\varnothing)=0。把 A 的全部 2^{n} 个子集的 f 函数值从小到大排成序列 B，给你 x，求 B 中第 1 次出现 x 时的下标。
分析：
设线性基的大小为 S。首先考虑 0 有几种方案：任取线性基外的一些数，共 2^{n-S} 种取法；每种取法对应线性基中的唯一一种，可以使得异或和为 0。因此 0 共有 2^{n-S} 种取法。
对于每个 x ，其取法和 0 可构成一一映射（从线性基中选取 x，如果一个数被选取了 2 次等于不选），也是 2^{n-S} 种取法。
因此我们只需要判断 x 在线性基可以异或出的数中是第几大即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
const int M = 32;
const int P = 10086;
int n, a[N], q;
int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % P) {
if (b & 1) ret = 1LL * ret * a % P;
}
return ret;
}
struct Linear_Base{
long long d[100]; int tot;
vector<long long> v;
void insert(long long x) {
for (int i = M; i >= 0; i--) {
if (!(x >> i)) continue;
if (!d[i]) {
d[i] = x; tot++; break;
}
x ^= d[i];
}
}
bool count(long long x) {
for (int i = M; i >= 0; i--) {
if (x & (1LL << i)) x ^= d[i];
}
return !x;
}
long long rank(long long x) {
if (!count(x)) return -1;
for (int i = 0; i <= M; i++) {
if (d[i]) v.push_back(i);
}
int sz = (int)v.size(); long long ans = 0;
ans++;
for (int i = 0; i < sz; i++) {
if ((x >> v[i]) & 1) ans += (1LL << i);
}
return ans;
}
}LB;
int main(int argc, const char * argv[]) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
LB.insert(a[i]);
}
scanf("%d", &q);
long long rk = LB.rank(q);
printf("%lld\n", (rk - 1) * ksm(2, n - LB.tot) % P + 1);
return 0;
}