定义
对于正整数x,将其拆成二进制表示,并且将二进制的每一位都看做坐标的每一位.就可以得到一个向量.然后在这个向量空间上定义加法运算为对应坐标进行异或运算,也就是等效于模2意义下的加法运算.
不难证明,这时整个空间成为了一个线性空间.因此,可以在这个空间上讨论线性相关,空间的基等一系列概念.对于给定的一个非负整数集合A生成的空间V,其在这种定义下的基向量组就称为线性基.
因为在研究线性基时没有必要将所有的非负整数都转化成坐标形式.所以,下面都用整数形式而非坐标形式讨论性质.
性质
- 对于集合中的两个数x,y.可以将x,y替换为x,x xor y.这时生成的空间不会发生变化.也就是线性基的大小不变.
证明:
假设一个数需要用y来表示,即
p=y \ xor \ t
根据异或运算的交换律和基本性质:
x \ xor \ x =0
则有
p=y \ xor \ t=x \ xor (x \ xor \ y) \ t
也就是p仍然能被表示出来,结论成立.根据这个性质,可以使用如下代码构造线性基:
inline void Insert(LL x){
int i=0;
for (i=50;i>=0;i--){
if (!(x>>i)) continue;
if (!p[i]) {p[i]=x; break;}
x^=p[i];
}
}
可以通过类似高斯消元的思想,使得只有第i个线性基的第i位为1,代码如下:
inline void Gauss(){
int i=0,j=0;
for (i=0;i<=50;i++){
if (!(p[i]>>i)) continue;
b[++cnt]=p[i];
for (j=i+1;j<=50;j++)
if ((p[j]>>i)&1) p[j]^=p[i];
}
}
求出线性基后,就可以利用其性质解决子集异或的问题了.
例题
[LOJ113]最大异或和
给出一个正整数集合,求出其子集的最大异或值.
线性基模板题.
构造出线性基后,从最高位向最低位枚举,如果异或上这一位线性基可以使答案变得更大,就异或这一位.
代码:
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
LL n,i,Ans,x;
LL p[64];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline LL read(){
LL p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Insert(LL x){
int i=0;
for (i=50;i>=0;i--){
if (!(x>>i)) continue;
if (!p[i]) {p[i]=x; break;}
x^=p[i];
}
}
int main(){
n=read();
for (i=1;i<=n;i++){
x=read(); Insert(x);
}
for (i=50;i>=0;i--)
if ((p[i]^Ans)>Ans) Ans^=p[i];
cout<<Ans<<endl;
return 0;
}
[LOJ114]K大异或和
给出一个正整数集合,求出其第k小的子集异或值.
先构造线性基,然后高斯消元.将不为0的基按照从低位到高位的顺序存起来.依次枚举线性基,当枚举到第i个时,如果k的第i位为1,就异或这个基.注意,当线性基的大小等于集合大小时,0不能被表示出来.
代码:
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 55
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int i;
LL n,m,k,x,cnt;
LL p[N],b[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline LL read(){
LL p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Insert(LL x){
int i=0,j=0;
for (i=50;i>=0;i--){
if (!(x>>i)) continue;
if (!p[i]) {p[i]=x; break;}
x^=p[i];
}
}
inline void Gauss(){
int i=0,j=0;
for (i=0;i<=50;i++){
if (!(p[i]>>i)) continue;
b[++cnt]=p[i];
for (j=i+1;j<=50;j++)
if ((p[j]>>i)&1) p[j]^=p[i];
}
// for (i=1;i<=cnt;i++) cout<<b[i]<<endl;
}
inline LL Query(){
int i=0;
LL Ans=0;
if (k>=(1ll<<cnt)) return -1;
for (i=0;i<=50;i++)
if (k&(1ll<<i)) Ans^=b[i+1];
return Ans;
}
int main(){
n=read();
for (i=1;i<=n;i++){
x=read(); Insert(x);
}
Gauss();
m=read();
for (i=1;i<=m;i++){
k=read();
if (cnt!=n) k--;
printf("%lld\n",Query());
}
return 0;
}
