线性基总结
|Word count:2.3k|Reading time:10min|Post View:
线性基能够接受$n$个数，并判定这些数是否能通过按位亦或和的方式表示出某个数，更能进一步表示出按位亦或和的第$K$小。线性基是一种另类的向量。
概念
张成
对于一个集合$S$，其张成定义为其中所有子集的异或和，记为$span(S)$。
根据异或的性质，易知其张成满足或存在：
封闭性：对于任何两个元素，其异或和唯一。
结合律：$(a \ xor \ b) \ xor \ c=a \ xor \ (b \ xor \ c)$。
单位元：$e=0$且$e \ xor \ a=a$。
逆元:$a \ xor \ a=e$。
则$span(S)$构成一个群。
线性相关
对于一个集合$S$，如果存在一个元素$S_j$，使得$S$在去除这个元素后得到的集合$S′$的张成不变，则称集合$S$线性相关，相应的，如果不存在这样的元素，则集合$S$线性无关。
线性基对于一个集合$S$，其线性基定义为满足线性无关的情况下的$span(S)$最小的子集，可以记为$span(S)′$，则有$span(span(S)′)$与$span(S)$等价。
线性基的构造
线性基的构造可以通过高斯消元或者一种类似贪心的算法完成，后者支持动态操作，所以在此处着重介绍。
已知集合$S$中最大的数在二进制意义下有$L$ 位，我们使用一个 $a[0…L]$来储存线性基，则该线性基的元素个数为$L$。
对于$a$数组，需要保证以下性质：
性质
$$a_i=0$$
则只有满足$j>i$的$a_j$的第$i$个二进制位可能为$1$；（性质一）
$$a_i≠0$$
整个$a$数组中只有$a_i$的第$i$个二进制位为$1$；（性质二）
$a_i$更高的二进制位一定为$0$；（性质三）
$a_i$更低的二进制位可能为$1$；
对于异或最大和的问题，我们可以通过贪心求解，即从高位到低位枚举是否有元素的二进制当前位为$1$，如果有，则亦或上该元素，而该构造方法则可以类比于上述操作中将该元素记录下来，而下文中构造的操作，同样保证了每一个元素均可以由线性基构造出来。
流程
对于每个新加入的元素$t$，从$L$枚举其二进制每一位$i$
$$ai≠0$$
那么将$t$异或上$a_i$（根据群的性质，可知该操作在保证张成不变的情况下使得$t$为$1$的位数尽可能少，并满足以上性质一以及性质二，且如果新插入一个元素已经在当前线性基的张成中，则在该操作后元素变为$0$）
$$ai=0$$
那么将$a$数组中每一个下标大于$i$且第$i$位为$1$的元素异或上$t$。将$t$异或上$a$数组中每一个下标小于$i$且第$i$位为$1$的元素。并将$t$插入$a_i$（根据群的性质，可知该操作在保证张成不变的情况下使得数组中二进制$1$的个数尽可能少）
相关题目
最大异或和
题解
直接套用线性基即可，如上所述，线性基实际上将贪心求解异或最大值的过程记录了下来，那么直接异或上所有线性基数组的值即可。
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=55;
ll B[MAXN];
int n,m;
vector<ll> V;
inline void insert(ll x)
{
for(int i=MAXN-1;i>=0;--i)
{
if((x&(1LL<<i))==0) continue;
if(B[i]) x^=B[i];
else
{
for(int j=0;j<i;++j)
{
if(x&(1LL<<j))
x^=B[j];
}
for(int j=i+1;j<MAXN;++j)
{
if(B[j]&(1LL<<i))
B[j]^=x;
}
B[i]^=x;
return;
}
}
}
inline ll qry(ll x)
{
ll s=0;
for(int i=0;i<V.size();++i)
{
if(x&(1LL<<i))
s^=V[i];
}
return s;
}
int main()
{
scanf("%d",&n);
ll x;
for(int i=1;i<=n;++i)
scanf("%lld",&x),insert(x);
ll cnt=0;
for(int i=0;i<MAXN;++i)
if(B[i])V.push_back(B[i]);
for(int i=0;i<V.size();++i)cnt^=V[i];
printf("%d\n",cnt);
return 0;
}
|
K小异或和
题解
以下分别表示所有的异或和的可能性，按从小到大顺序排序（$L=3$,以下第一列数字表示$a$数组的下标）
二进制表示
1 第1小 1
2 第2小 10
1 xor 2 第3小 11
3 第4小 100
1 xor 3 第5小 101
2 xor 3 第6小 110
1 xor 2 xor 3 第7小 111
|
观察可知，$K$小异或和即为$K$的二进制分解中为$1$的位置在$a$中作为下标的线性基的异或和。
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=55;
ll B[MAXN];
int n,m;
vector<ll> V;
inline void insert(ll x)
{
for(int i=MAXN-1;i>=0;--i)
{
if((x&(1LL<<i))==0) continue;
if(B[i]) x^=B[i];
else
{
for(int j=0;j<i;++j)
{
if(x&(1LL<<j))
x^=B[j];
}
for(int j=i+1;j<MAXN;++j)
{
if(B[j]&(1LL<<i))
B[j]^=x;
}
B[i]^=x;
return;
}
}
}
inline ll qry(ll x)
{
ll s=0;
for(int i=0;i<V.size();++i)
{
if(x&(1LL<<i))
s^=V[i];
}
return s;
}
int main()
{
scanf("%d",&n);
ll x;
for(int i=1;i<=n;++i)
scanf("%lld",&x),insert(x);
ll cnt=0;
for(int i=0;i<MAXN;++i)
if(B[i])V.push_back(B[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%lld",&x);
if(V.size()!=n) --x;
if(x>=(1LL<<V.size()))
printf("-1\n");
else printf("%lld\n",qry(x));
}
return 0;
}
|
HAOI2017 八纵八横
题解
非常非常具有代表性的一个题目。
在$dfs$树上，一条非树边代表一个简单环，所以一个新增的边最多带来一个新环，而这个新环，肯定是经过这条新边，从$x$走到$y$，再走回$x$的路径所构成的一个环。因为$xor$的特性，所以我们可以用$x$到$root$的路径 + $y$到$root$的路径 + 新边来异或出这个环的异或值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
const int N = 1e3+1;
bitset<1024>a,e2[N],v[N],M[N],mat[N],dis[N];
int n,m,Q,head[N],cnt,cnt1,fa[N],e1[N][2],now,huan[N];
char opt[N],ch[N];
bitset<1024> readb()
{
bitset<1024>t;t.reset();
scanf("%s",ch);
int len=strlen(ch);
for(int i=0;i<len;++i)
t[len-i-1]=ch[i]-'0';
return t;
}
struct nd{int ne,to;bitset<1024>w;}e[N*2];
void in(int x,int y,bitset<1024>w)
{e[++cnt].to=y;e[cnt].w=w;e[cnt].ne=head[x];head[x]=cnt;return;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void dfs(int x,int f)
{
for(int i=head[x];i;i=e[i].ne)
if(e[i].to!=f)
{
dis[e[i].to]=dis[x]^e[i].w;
dfs(e[i].to,x);
}
}
int update(int x,bitset<1024>y)
{
now=0;
for(int i=0;i<N;++i)
if(M[i][x]&&mat[i].none())
{
now=i;
break;
}
if(!now)
for(int i=0;i<N;++i)
if(M[huan[i]][x]&&huan[i]!=0)
{
now=huan[i];
huan[i]=0;
break;
}
for(int i=0;i<N;++i)
if(now!=i&&M[i][x])
{
mat[i]=mat[i]^mat[now];
M[i]=M[i]^M[now];
}
mat[now]^=y;
for(int i=N;i>=0;--i)
if(mat[now][i])
{
if(!huan[i]){huan[i]=now;break;}
else mat[now]=mat[now]^mat[huan[i]],M[now]=M[now]^M[huan[i]];
}
return 0;
}
void put()
{
bitset<1024>ans;
ans.reset();
for(int i=N-1;i>=0;--i)
if(ans[i]==0&&huan[i])
ans^=mat[huan[i]];
char *tmp,tong[N];
if(ans.none()) puts("0");
else
{
tmp=tong;
for(int i=N-1;i>=0;--i)
if(ans[i])
{
for(int j=i;j>=0;--j)
*(tmp++)=ans[j]+'0';
break;
}
*(tmp++)='\0';
puts(tong);
}
}
int main()
{
freopen("eights.in","r",stdin);
freopen("eights.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;++i)fa[i]=i;
for(int i=1;i<N;++i)M[i][i]=1;
for(int i=1,x,y;i<=m;++i)
{
scanf("%d%d",&x,&y);
a=readb();
if(gf(x)==gf(y))
{
e1[++cnt1][0]=x;
e1[cnt1][1]=y;
v[cnt1]=a;
}
else
fa[gf(x)]=gf(y),in(x,y,a),in(y,x,a);
}
dfs(1,-1);
int cntn=cnt1;
for(int i=1;i<=cnt1;++i)
update(i,dis[e1[i][0]]^dis[e1[i][1]]^v[i]);
put();
for(int i=1,x,y;i<=Q;++i)
{
scanf("%s",opt);
if(opt[1]=='d')
{
scanf("%d%d",&x,&y);
a=readb();
e1[++cnt1][0]=x;e1[cnt1][1]=y,e2[cnt]=a;
v[cnt1]=a;
update(cnt1,dis[e1[cnt1][0]]^dis[e1[cnt1][1]]^v[cnt1]);
}
if(opt[1]=='h')
{
scanf("%d",&x);
a=readb();
update(x+cntn,v[x+cntn]^a);
v[x+cntn]=a;
}
if(opt[1]=='a')
{
scanf("%d",&x);
update(x+cntn,dis[e1[x+cntn][0]]^dis[e1[x+cntn][1]]^v[x+cntn]);
v[x+cntn]=0;
}
put();
}
}
|
