线性基学习笔记
前言:
如果你不会线性基，希望能对你有点帮助。
作者较菜，请大佬轻表。
请大家多多支持，谢谢
<!--more-->
定义：
基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。
同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。(摘自百度百科)
性质：
- 线性基能相互异或得到原集合的所有相互异或得到的值。
- 线性基没有异或和为0的子集。
- 线性基的值域与原数组的值域相同 。
作用：
线性基是常用来解决子集异或一类题目的算法。
线性基可以在log的时间复杂度求出一个集合的子集异或(min,max.......)
构造：
插入一个数x：
若干数的线性基是一组数，其中
为最高位的1在第x位的值。
对于一个数x，从最高位到0枚举，如果x的这一位上是1，那么分两类。
如果这一位的a数组为空，说明没有这样的情况，那么就把这一位的a数组赋值成x，注意然后要break
如果这一位的a数组不为空，说明已经出现这种情况,那么x异或上这一位的a数组上的值，然后继续。
void insert(int x)
{
for(int i=20;i>=0;i--)
if(x&(1<<i))
{
if(!a[i])
{
a[i]=x;
return;
}
x^=a[i];
}
}查询能否xor出x这个数：
这相当于就是插入的逆操作。
就是对于一个数x，从最高位到0枚举，如果x的这一位上是1，那么分两类。
如果这一位的a数组为空，说明没有出现过这样的情况，直接返回false
否则x异或上这一位的a数组上的值，然后继续。
bool find(int x)
{
for(int i=20;i>=0;i--)
if(x&(1<<i))
{
if(!a[i])return false;
x^=a[i];
}
return true;
}查询最大值：
我们从最高位开始，记录一个最大值ans，ans=max(ans,a[i]);
显然，每次操作后答案不会变劣，所以是正确的。
inline int query()
{
res=0;
for(int i=20;i>=0;i--)
res=max(res,res^a[i]);
return res;
}查询最小值：
这就相对较简单了，和最大值的思想一样，每次异或上a[i]答案只会变大，所以最小值就是min(a[i])
int query()
{
for(int i=0;i<=20;i++)
if(a[i])return a[i];
}组合：
线性基可以和很多东西组合，比如线段树，st表等等。
CF1100F Ivan and Burgers 这题就是线性基和其他东西结合。
题意：
给你n个数，每次查询这个区间，问着个区间的最大异或值。
题解：
这题可以很好的和线段树结合起来，只需线性基的插入，合并，找最大即可。
查询答案可以用线段树上二分。
但由于时间复杂度是三只log的，过不了。
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
const int N=500005;
int n,m,l,r;
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int ret=0,f=0;
char c=gc();
while(!isdigit(c))
{
if(c=='-')f=1;
c=gc();
}
while(isdigit(c))
{
ret=ret*10+c-48;
c=gc();
}
if(f)return -ret;
return ret;
}
struct node{
int res,a[25];
inline void insert(int x)
{
for(int i=20;i>=0;i--)
if(x&(1<<i))
{
if(!a[i]){a[i]=x;return;}
else x^=a[i];
}
}
inline int query()
{
res=0;
for(int i=20;i>=0;i--)
res=max(res,res^a[i]);
return res;
}
}xu,T[N*4];
void ins(int x)
{
if(!x)return;
int hb=log2(x);
if(!xu.a[hb])xu.a[hb]=x;
if(xu.a[hb])ins(x^xu.a[hb]);
}
inline node merge(node a,node b)
{
xu=b;
for(int i=0;i<=20;i++)
ins(a.a[i]);
return xu;
}
void build(int nod,int l,int r)
{
if(l==r)
{
T[nod].insert(read());
return;
}
build(nod*2,l,mid);
build(nod*2+1,mid+1,r);
T[nod]=merge(T[nod*2],T[nod*2+1]);
}
node find(int nod,int l,int r,int L,int R)
{
if(L==l&&R==r)return T[nod];
if(R<=mid)return find(nod*2,l,mid,L,R);
else if(L>mid)return find(nod*2+1,mid+1,r,L,R);
else return(merge(find(nod*2,l,mid,L,mid),find(nod*2+1,mid+1,r,mid+1,R)));
}
int main()
{
n=read();
build(1,1,n);
m=read();
while(m--)
{
l=read();r=read();
node ans=find(1,1,n,l,r);
printf("%d\n",ans.query());
}
return 0;
}
这题还可以用线性基和整体二分配合使用。（这里不过多解释）
正解是线性基+贪心。
表示1-i，中j这个位上的数
表示1-i，中j这个位上的数最接近i的是哪个位置
然后贪心一下就好了
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m,b[N][25],p[N][25];
#define gc getchar
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
void get(int x,int k,int r)
{
for(int i=20;i>=0;i--)
if(x&(1<<i))
{
if(!b[r][i])
{
b[r][i]=x;
p[r][i]=k;
return;
}
if(p[r][i]<k)
{
swap(p[r][i],k);
swap(x,b[r][i]);
}
x^=b[r][i];
}
}
int solve(int l, int r)
{
int ans=0;
for(int i=20;i>=0;i--)
if(p[r][i]>=l)ans=max(ans,ans^b[r][i]);
return ans;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int x=read();
memcpy(b[i],b[i-1],sizeof(b[i]));
memcpy(p[i],p[i-1],sizeof(p[i]));
get(x,i,i);
}
m=read();
while(m--)
{
int l=read(),r=read();
printf("%d\n",solve(l,r));
}
return 0;
}例题：
题目：【模板】线性基
这题就是给你n个数，求他们的最大异或值是多少。
题解：
这不就是线性基的模板题吗，只要一个插入，一个查询最大值即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,ans,p[55];
void find(int x)
{
for(int i=51;i>=0;i--)
{
if((x>>i)==0)continue;
if(!p[i])
{
p[i]=x;
break;
}
x^=p[i];
}
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
find(x);
}
for(int i=51;i>=0;i--)
if((ans^p[i])>ans)ans^=p[i];
cout<<ans;
return 0;
}题目：[BJWC2011]元素
给定一些矿石的编号与价值,输出得到最大的价值和,要求选定物品的编号异或之和不为0.
题解：
这题的做法是线性基+贪心
贪心就是将所有矿石的魔力值降序排列。然后把元素编号x插入线性基里去维护。
若是插入结束后 x 的值不为 0 说明选择它不会导致选择的矿石元素编号异或起来为0
那我们就把魔力值累加起来就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans,p[105];
struct node{
int id,val;
}a[2005];
bool cmp(node a,node b)
{
return a.val>b.val;
}
bool find(int x)
{
for(int i=105;i>=0;i--)
{
if((x&(1ll<<i))==0ll)continue;
if(p[i])x^=p[i];
else{p[i]=x;return true;}
}
return false;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i].id,&a[i].val);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
if(find(a[i].id))ans+=a[i].val;
cout<<ans;
}再来一题模板题，考验一下大家。
题目：牛客xor序列
小a有n个数，他提出了一个很有意思的问题：他想知道对于任意的x, y，能否将x与这n个数中的任意多个数异或任意多次后变为y
题解：
首先知道一个性质：x^y=z z^x=y z^y=x
那不就是简单的插入和判断x^y是否存在吗
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,y,m,p[55];
void add(int x)
{
for(int i=50;i>=0;i--)
{
if((x>>i)==0)continue;
if(!p[i])
{
p[i]=x;
break;
}
x^=p[i];
}
}
bool pd(int x)
{
for(int i=50;i>=0;i--)
{
if((x>>i)==0)continue;
if(!p[i])return false;
x^=p[i];
}
return true;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
add(x);
}
scanf("%lld",&m);
while(m--)
{
scanf("%lld%lld",&x,&y);
if(pd(x^y))puts("YES");
else puts("NO");
}
return 0;
}如果你觉得简单，你可以去做一下牛客知识点练习 > 线性基 。
请大家多多支持，谢谢。
携程开奖26人在聊