线性基学习笔记
线性基在 OI
中大部分时候是一种基于贪心的数据结构，主要用于解决异或有关的问题，其正确性证明需要基于向量等线性代数内容。
免责声明
本文仅介绍其在 OI
中的常见应用，内容将尽量基于实用性与浅显易懂的感性理解进行讲解，不会对其原理做出任何详细说明，请酌情阅读。如需详细讲解与证明请出门左转
OI-Wiki。
下文只讨论线性基在解决异或问题中的应用。
定义
对于可重集 ，如果存在极小的 满足 的所有子集的异或和构成的集合与 所有子集的异或和构成的集合相同，那么
就是 的线性基。
显而易见地， 的大小不会超过
（
是值域）（因为每一位只需要一个贡献的数）。
线性基的构造
开一个长为
的数组来表示线性基，第
位表示作为贡献第
位的数是什么。
考虑将
中所有元素写作二进制，并以任意顺序插入线性基。
插入一个数
时，从二进制最高位开始重复以下步骤：
- 如果 的第 位为 ：
- 如果线性基这个位置没有数，将
插入到这里，结束循环。
- 否则设线性基这个位置的数是 ，则 ，进入下一位。
- 否则进入下一位。
如果最终仍然没有插入进去，则插入失败。
感性理解正确性
从整体上来讲，必要性是显然的：所有没有插入进线性基的数它必定可以表示为线性基中一些数的异或和（就是它试图插入的所有位置上的数），因此线性基一定可以表示原集合中的所有异或和。
从递推的角度来讲：
- 在线性基中一个元素都没有的情况下，原集合也只有空集一种情况，满足充要性。
- 设线性基 中已经插入了 个元素
且线性基子集异或和与原集合子集异或和一致，现在新插入 ，实际插入的 是 ，那么对于
任意子集 ，它一定在线性基的所有异或和中只出现了一次（否则一定可以删掉一个元素而线性基可表示的结果不变）设为
，那么
也一定可以且只能用 表示（异或两次就消掉即可）。
综上，用上述方式构造的线性基满足充要性，正确性成立。
求解问题
一般用于求解最大/最小异或和。
求解过程实质也是贪心：从高位开始贪心，如果要最大化那么这一位尽可能取
，反之取 。
对于最小异或和，如果存在数没有插入成功，则最小异或和为 （显然）。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| const int DD=63;
struct LinerChicken{
private:
vector<ll> C;
public:
LinerChicken():C(DD+1){}
void ins(ll x){
for(int i=DD;~i;--i)if(x&(1ll<<i)){
if(!C[i])return C[i]=x,void();
x^=C[i];
}
}
ll qry(){
ll ans=0;
for(int i=DD;~i;--i)ans=std::max(ans,ans^C[i]);
return ans;
}
};
|
例题
题意：有
个物品，每个物品有两个属性 ，你要从其中选出若干个物品使得这些物品的任意非空子集
异或和不为 。求最大的 之和。
把所有物品按照
递减排序并插入线性基，每次如果插入成功则加上这个物品的收益。证明略。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using std::vector;
typedef vector<int> vi;
typedef long long ll;
const int DD=63;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
struct LinerChicken{
private:
vector<ll> C;
public:
LinerChicken():C(DD+1){}
bool ins(ll x){
for(int i=DD;~i;--i)if(x&(1ll<<i)){
if(!C[i])return C[i]=x,1;
x^=C[i];
}
return 0;
}
};
int main(){
int n=read();
vector<std::array<ll,2>> a(n+1);
for(int i=1;i<=n;++i)a[i][0]=read<ll>(),a[i][1]=read();
std::sort(a.begin()+1,a.end(),[&](std::array<ll,2> x,std::array<ll,2> y){return x[1]>y[1];});
ll ans=0;
LinerChicken C;
for(int i=1;i<=n;++i)if(C.ins(a[i][0]))ans+=a[i][1];
printf("%lld\n",ans);
return 0;
}
|
题意：给定无向图，边有边权，求
到
的路径中的边权的最小异或和。
考虑如果经过了一条边两次就相当于没有经过，因此我们可以不断地绕到经过图上的某些环上再原路返回，这样相当于异或上了这个环的异或和。
于是我们随意求出一个生成树，算出 到每个点生成树的前缀异或和 ，则对于非树边 ，向线性基中插入 。
最终求答案时使 初始值为
即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<bits/stdc++.h>
#define int long long
using std::vector;
typedef vector<int> vi;
typedef long long ll;
typedef std::array<int,2> pii;
const int DD=63;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
struct LinerChicken{
private:
vector<ll> C;
public:
LinerChicken():C(DD+1){}
void ins(ll x){
for(int i=DD;~i;--i)if(x&(1ll<<i)){
if(!C[i])return C[i]=x,void();
x^=C[i];
}
}
ll qry(ll x){
ll ans=x;
for(int i=DD;~i;--i)ans=std::max(ans,ans^C[i]);
return ans;
}
};
signed main(){
int n=read(),m=read();
vector<vector<pii>> G(n+1);
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
G[u].push_back({v,w}),G[v].push_back({u,w});
}
vi xr(n+1);
vector<bool> vis(n+1);
LinerChicken C;
auto dfs=[&](auto dfs,int u,int f) -> void {
vis[u]=1;
for(auto V:G[u]){
int v=V[0],w=V[1];
if(v!=f){
if(!vis[v])xr[v]=xr[u]^w,dfs(dfs,v,u);
else C.ins(xr[u]^xr[v]^w);
}
}
};dfs(dfs,1,0);
printf("%lld\n",C.qry(xr[n]));
return 0;
}
|
题意：求区间最大异或和。 个数 询问值域
。
详见这篇文章。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using std::vector;
typedef vector<int> vi;
typedef long long ll;
const int DD=20;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
struct LinerChicken{
private:
vector<int> C,P;
public:
LinerChicken():C(DD+1),P(DD+1){}
void ins(int p,int x){
for(int i=DD;~i;--i)if(x&(1<<i)){
if(!C[i])return C[i]=x,P[i]=p,void();
else if(P[i]<p)std::swap(C[i],x),std::swap(P[i],p);
x^=C[i];
}
}
int qry(int l){
int ans=0;
for(int i=DD;~i;--i)if(P[i]>=l)ans=std::max(ans,ans^C[i]);
return ans;
}
};
int main(){
int n=read();
vi a(n+1);
for(int i=1;i<=n;++i)a[i]=read();
int Q=read();
vector<std::array<int,3>> q(Q+1);
for(int i=1;i<=Q;++i)q[i][0]=read(),q[i][1]=read(),q[i][2]=i;
std::sort(q.begin()+1,q.end(),[&](std::array<int,3> x,std::array<int,3> y){return x[1]==y[1]?x[0]<y[0]:x[1]<y[1];});
LinerChicken C;
vi ans(Q+1);
for(int i=1,j=1;i<=n;++i){
C.ins(i,a[i]);
for(;j<=Q&&q[j][1]<=i;++j)ans[q[j][2]]=C.qry(q[j][0]);
}
for(int i=1;i<=Q;++i)printf("%d\n",ans[i]);
return 0;
}
|