线性基学习笔记

前言

这几天遇到了一道线性基的题目，补一下之前的知识点。

概念

线性基是一个数的集合，并且每个序列都拥有至少一个线性基。

三大性质

1. 线性基能相互异或得到原集合的所有相互异或得到的值。
2. 线性基是满足性质$1$的最小的集合。
3. 线性基没有异或和为$0$的子集。

构造

设一个数组$d$表示序列$a$的线性基，下标从$0$开始算，对于序列中的每一个数$x$，尝试将它插入线性基里面去。

void insert (LL x) {fd (i , 60 , 0) {if (x & (1ll << i)) {if (d[i]) x ^= d[i];else {d[i] = x;return;}}}
}

我们设 x ( 2 ) x_{(2)} x(2)​为$x$的二进制数。
由此我们还可以推理出：若 d i ! = 0 d_i != 0 di​!=0，则 d [ i ] ( 2 ) d[i] _ {(2)} d[i](2)​的$i+1$位一定位$1$并且 d [ i ] ( 2 ) d[i] _ {(2)} d[i](2)​的最高位就是$i+1$
补充一下关于异或的一点点小知识
$a⨁b⨁c=0\Leftarrow \Rightarrow a⨁b=c\Leftarrow \Rightarrow a⨁c=b\Leftarrow \Rightarrow b⨁c=a$

应用

求序列中元素异或值的最大值。

题目链接

题目描述

给一个长度为$n$的序列，你可以从中取若干个数，使得它们异或值最大.

数据规模

n ≤ 50 s i ≤ 2 50 n \\leq 50 \\ s_i \\leq 2^{50} n≤50 si​≤250

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
int n;
long long a , d[65];
void insert (LL x) {fd (i , 60 , 0) {if (x & (1ll << i)) {if (d[i]) x ^= d[i];else {d[i] = x;return;}}}
}
void fans () {long long ans = 0;for (int i = 60 ; i >= 0 ; i --) {ans = max (ans , ans ^ d[i]);}printf ("%lld" , ans);
}
int main () {scanf ("%d" , &n);for (int i = 1 ; i <= n ; i ++) {scanf ("%lld" , &a);insert (a);}fans ();
}

求序列中元素异或值的第$k$小值。

题目描述

给一个长度为 的序列，你可以从中任取若干个数进行异或，求其中的第 小的值。

数据规模

1 ≤ n , m ≤ 1 0 5 1 \\leq n , m \\leq 10 ^ 5 1≤n,m≤105 0 ≤ s i ≤ 2 50 0 \\leq s_i \\leq 2 ^ {50} 0≤si​≤250

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
#define LL long long
using namespace std;
LL ans[105] , n , m , k , d[155] , cnt;
LL read () {LL val = 0 , fu = 1;char ch = getchar ();while (ch < '0' || ch >'9') {if (ch == '-') fu = -1;ch = getchar ();}while (ch >= '0' && ch <= '9') {val = val * 10 + (ch - '0');ch = getchar ();}return val * fu;
}
void insert (LL x) {fd (i , 50 , 0) {if (x & (1ll << i)) {if (d[i]) x ^= d[i];else {d[i] = x;return;}}}
}
void rebuild () {fd (i , 50 , 0) {for(int j = i - 1 ; j >= 0 ; j --) {if (d[i] & (1ll << j))d[i] ^= d[j];}}fu (i , 0 , 50) {if(d[i]) ans[cnt++] = d[i];}
}
void kth () {LL sum = 0;if (cnt != n) k --;if(k >= (1ll << cnt)) {printf ("-1\\n");return;}fd (i , 50 , 0) {if (k & (1ll << i)) sum ^= ans[i];}printf ("%lld\\n" , sum);
}
int main () {LL a;n = read ();fu (i , 1 , n) {a = read ();insert (a);}rebuild ();m = read ();fu (i , 1 , m) {k = read ();kth ();}
}