【学习笔记】浅谈异或线性基

1、前言

Upd on 2022.8.19：添加线性基的求交与求并。

Upd on 2023.5.9：日报过审，于是修了格式，改了一些以前写的~~过于迷惑的语言表述~~。

Upd on 2023.5.12：采纳魏老师建议，添加带删除线性基部分，同时增加一道例题。

线性基作为一个工具，在很多跟异或有关的题目中都有广泛的应用。

提前介绍一个异或（用

\oplus

表示）的性质。

若

a\oplus b\oplus c=0

，则

a\oplus b=c

。

因此，若

a\oplus b=c

，则

a\oplus c=b

。

2、线性基基本概念

定义：给定数集

S

，以异或运算张成的数集与

S

相同的极大线性无关集，称为原数集的一个线性基。

通俗地说，线性基是一个数的集合。每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原序列中的任何一个数。

3、线性基重要性质

性质一

原序列的任意一个数都可以由线性基内部的一些数异或得到。

性质二

线性基内部的任意数异或起来都不能得到

0

。

性质三

线性基内部的数个数唯一；且在保持性质一的前提下，数的个数是最少的。

下面给出三个性质的证明。

性质二

用反证法，设

d_i\oplus d_j\oplus d_k=0

（

d_k

比

d_i,d_j

更晚插入线性基），则

d_i\oplus d_j=d_k

。由于

d_k

能由

d_i\oplus d_j

得到，故

d_j

不能进入线性基。

故假设不成立，线性基中不存在任何数异或起来可以得到

0

。

证毕。

性质一

对将插入的数

x

分类讨论。

x

不能成功插入线性基时，显然

x

异或上线性基中的若干个数的结果为

0

。那么就能得到：

x\oplus d_i\oplus d_j\oplus d_k\oplus \dots=0

，则有：

d_i\oplus d_j\oplus d_k\oplus \dots=x

。所以，若

x

不能成功插入线性基，是因为当前线性基里面的一些数异或的结果等于

x

。

x

可以成功插入线性基时，设

x

插入到了线性基的第

i

个位置。显然，插入前可能异或若干个数，则有

x\oplus d_a\oplus d_b\oplus d_c\oplus \dots=d_i

，那么

d_i\oplus d_a\oplus d_b\oplus d_c\oplus \dots=x

。所以

x

也可以由线性基里面的若干个数异或得到。

综上，原序列的任意一个数都可以由线性基内部的一些数异或得到。

证毕。

性质三

若序列里面的所有元素都可以插入到线性基里面，则不管用什么顺序将序列里的数插入线性基，线性基中的元素一定与原序列元素数量相同。

若序列里面的一些元素不能插入到线性基里面，则设

x

不能插入线性基，一定满足形如

d_i\oplus d_j\oplus d_k=x

的式子。尝试将插入顺序改变为

d_i,d_j,x,d_k

，则

d_k

就不可能插入成功，原因很简单，留给读者自己思考。

通俗地说，原来是

x

插不进去，改变顺序后，则是

d_k

插不进去。即对于插不进去的元素，改变插入顺序后，要么还是插不进去；要么就是插进去了，同时另一个原来插进去的元素插不进去了。因此，可以插进去的元素数量一定是固定的。

若去掉线性基里面的任一个数，都会使得原序列里的数无法通过用线性基里的元素异或得到，没有多余的元素。所以线性基的元素个数在保持性质一的前提下，一定是最少的。

证毕。

4、线性基基本操作

插入

设数组

p

表示序列

\{a_n\}

的线性基，待插入数为

x

，下标从

0

开始。

将

x

转为二进制，从它的高位开始，如果当前位为

1

，并且线性基

p

的第

i

位上没有数，那就赋成当前值

x

。否则，将

x

异或

p_i

。

CPP

typedef long long ll; //后同
void upd(ll x) {
    for(int i=60;i>=0;--i)
        if(x>>i&1) {
            if(!p[i]) {p[i]=x;break;}
            x^=p[i];
        }
}

求最大值

在一个序列

\{a_n\}

中，取若干个数，求它们的最大异或和。事实上，这题就是 P3812 【模板】线性基。

首先构造出这个序列的线性基。

接着采取贪心的思想，从线性基的最高位开始，若当前的答案异或线性基的这个元素可以变得更大，那么就异或它。答案的初值为

0

。

CPP

ll getmx() {
    ll ans=0;
    for(int i=60;i>=0;--i)
        if((ans^p[i])>ans) ans^=p[i];
    return ans;
}

求最小值

如果是求用线性基

p

内的元素能异或出的最小值，那么就是最小的

p_i

了。其正确性显然，因为最小的

p_i

无论异或谁都会变大。

如果是求整个序列能异或出的最小值的话，要另外检查有没有元素不能插入线性基，如果有，那么最小值就是

0

，否则依然是最小的

p_i

。

代码略。

求 $k$ 小值

从一个序列中取任意元素进行异或，求能异或出的所有数字中第

k

小的那个。

首先处理这个序列的线性基

p

，对于每一个

p_i

，枚举

j=i\sim 1

，如果

p_i

二进制的第

j

位为

1

，那么

p_i

异或上

p_{j-1}

。

将

k

先转成二进制，假如第

i

位为

1

，则

ans

异或线性基中第

i

个元素（注意不是直接异或

p_{i-1}

）。

CPP

inline void prework() {
	for(int i=1;i<=60;++i)
		for(int j=1;j<=i;++j)
			if(p[i]&(1LL<<j-1)) p[i]^=p[j-1];
}
inline ll getkth(int k) {
	if(k==1&&size<n) return 0;
	if(size<n) --k;
    //n表示序列长度，size表示线性基内部元素个数
	prework();
	ll ans=0;
	for(int i=0;i<=60;++i)
		if(p[i]) {
			if(k&1) ans^=p[i];
			k>>=1;
		}
	return ans;
}

询问存在性

判断数

x

能否被当前线性基中元素异或得到。

把

x

尝试插入进线性基，假如可以插入，说明不能异或得到，假如插不进去，则说明可以异或得到。

代码略。

线性基求并

很简单。假设有两个线性基

A,B

，显然，将

A

的每一个元素插入线性基

B

即可，插不进去则忽略。

代码略。

线性基求交

求一个线性基，它一定能被两个线性基

A,B

分别表示。

如果

B_i

能被

\{A_{i=1\sim x}\}

与

B_{j=1\sim i-1}

线性表示出来，就把

\bigoplus_{i=1}^{x}A_i

或者

\bigoplus_{j=1}^{i-1}B_j

（二者只能加入其一）加入答案的线性基中。

由于有复制操作，为方便，使用结构体。

CPP

struct node {
	ll p[60];
	node() {memset(p,0,sizeof p);}
};
node d,all;
node merge(const node&a,const node&b) {
	node res;
	d=a,all=a; //all表示目前所有可用的低位基 
	ll k; //k是把Bi和它的低位削减至0所用到的A的异或和 
	for(int i=0;i<60;++i) {
		if(!b.p[i]) continue;
		ll v=b.p[i];
		k=0;
		int j;
		for(j=i;j>=0;--j)
			if(1LL<<j&v) {
				if(all.p[j]>0)
                    v^=all.p[j],k^=d.p[j];
				else break;
			}
		if(!v) res.p[i]=k;
		else all.p[j]=v,d.p[j]=k;
	}
	return res;
}

5、带删除线性基

采纳魏老师建议，增加此版块。

在线的不太会就不写了，也算是给后人留个坑填嘛（

将操作离线，维护

p_i

表示线性基内的第

i

个元素，

t_i

表示这个元素的最晚删除时间。

插入

与不带删除的线性基基本类似。根据贪心思想，我们希望能使高位基的删除时间较晚（否则，到了删除时间，高位基无法选择，会使答案变劣）。

因此，从插入的数的高位开始枚举，能插就插。

CPP

void upd(ll x,int time) { //插入数x,该数最晚删除时间为time
    for(int i=60;i>=0;--i)
        if(x>>i&1) {
            if(t[i]<time) {
                swap(time,t[i]);
                swap(x,p[i]);
            }
            if(time==0) break;
            x^=p[i];
        }
}

求最大值

这里的“最大值”含义上文已有描述，故不再过多赘述。

只需在不带删除的线性基的基础上加上一个关于时间的特判。

CPP

ll getmx(int time) { //查询当前时间为time时的最大值
    ll ans=0;
    for(int i=60;i>=0;--i)
        if(time<t[i])
            if((ans^p[i])>ans) ans^=p[i];
    return ans;
}

6、线性基复杂度

这里介绍一下线性基的复杂度。

时间复杂度

插入：upd() 函数从

60

循环到

0

，而

a_i

的值域为

2^{60}

，故时间复杂度为

O(\log N)

（

N

表示值域，

\log

均以

2

为底，下同）。

求最大值：读入数据需要

O(n)

的时间，插入的复杂度上面讲过了，总复杂度为

O(n\log N)

（

n

为原序列长度，下同）。

求最小值：检查需要

O(n)

的时间，加上判断能否插入，总复杂度为

O(n\log N)

。

求

k

小值：主要是 prework() 函数较为耗时。总复杂度为

O(\log^2N)

。

判断数

x

能否被当前线性基中元素异或得到：也就是尝试插入，复杂度

O(\log N)

。

求并：很显然，

O(\log^2N)

。

求交：从代码里可看出，两重循环，故也是

O(log^2N)

。

空间复杂度

显然，需要一个构造线性基的辅助数组，空间复杂度为

O(\log N)

。

7、线性基例题

这里，以两道例题，让读者更加熟悉线性基的用法。

以下每一道例题，笔者的讲解都比较简略，故给出完整的参考代码以加深理解。如果读者觉得难以接受，可以参看对应题目的题解。

还是选主题库的题吧，怕被没绑账号的人喷，想要做非主题库题目，可以参考后面给的习题单（

例一：[BJWC2011]元素

算法分析：线性基，排序，贪心。

首先按照矿石的

\text{Magic}

值降序排序，接着把元素的编号扔到线性基里面去。如果

\text{Number}_i

能加入线性基，则将

ans

加上

\text{Magic}_i

。

CPP

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

struct node {
	ll a;
	int b;
	friend bool operator< (const node &a,const node &b) {
		return a.b>b.b;
	}
} a[1010];

ll p[100];
int n,ans;
inline void upd(ll x,int y) {
	for(int i=60;~i;--i)
		if(x>>i&1) {
			if(!p[i]) {p[i]=x,ans+=y;break;}
			x^=p[i];
		}
}

int main () {
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i].a>>a[i].b;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i) upd(a[i].a,a[i].b);
	cout<<ans<<endl;
	return 0;
}

例二：[TJOI2008]彩灯

算法分析：线性基，字符串。

这是一题很明显的线性基，由于线性基可以通过异或的方式，得到原序列中的任意元素，所以我们只要直接求线性基就可以了。设线性基的长度为

ans

，则答案为

2^{ans} \bmod 2008

。

CPP

#include <string>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
string s;

ll p[100];
inline void upd(ll x) {
	for(int i=60;~i;--i)
		if(x&1LL<<i)
			if(p[i]) x^=p[i];
			else {p[i]=x;break;}
}

int n,m;
int main () {
	cin>>n>>m;
	while(m--) {
		cin>>s;
		ll x=0;
		for(int i=0;i<n;++i) x|=(ll)(s[i]=='O')<<i;
		upd(x);
	}
	int ans=0;
	for(int i=60;~i;--i)
		if(p[i]) ++ans;
	cout<<(1LL<<ans)%2008;
	return 0;
}

8、线性基扩展应用

有的时候，题目里面不仅仅有线性基，而更是将其与树论、图论等知识结合起来，这就要求我们不仅会理论知识，而且要触类旁通。

下面，给出三道更难的例题。

例三：[CQOI2013] 新 Nim 游戏

算法分析：线性基，排序，博弈论。

显然，~~根据小学奥数知识~~根据 Nim 游戏的结论，不能给后手任何让石子数异或为

0

的机会，所以在插入前先询问该数是否会让石子异或和变为

0

，若会，则把这堆石子拿掉，否则加入线性基里，这样后手无论如何都不能让石子异或和变为

0

。值得吐嘈的是，先手必胜，所以输出

-1

是没分的。

关于最小值的问题，跟例一一样，先排序即可。

CPP

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll; 
int n,a[110],b[110];
ll s,ans;
int main () {
	cin>>n;
	for(int i=1;i<=n;++i)
        cin>>a[i],s+=1LL*a[i];
	sort(a+1,a+1+n);
	for(int i=n;i;--i) {
		int t=a[i];
		for(int j=30;~j;--j)
			if(a[i]>>j&1)
				if(b[j]) a[i]^=b[j];
				else {b[j]=a[i];break;}
		if(a[i]) ans+=1LL*t;
	}
	cout<<s-ans;
	return 0;
}

例四：[WC2011]最大 XOR 和路径

算法分析：线性基，图形结构，DFS。

先假设选择了一条从

1

到

n

的主路径，然后在这条路径上向外拓展。显然，只有环对答案有影响，因为非环的边一定会走两次，异或和为

0

。

因为图是联通的，所以可以经过任意环，把所有的环的异或值扔到线性基里，然后再考虑选择哪一条路径。注意到，若从

1

到

n

有多条路径，其实这些路径也构成了环，也会被加入到线性基里，这时候随便选一条路径即可。

如何找环？其实很简单，通过在 DFS 树上通过返祖边找到简单环的方法，很容易能找到环。

CPP

#include<iostream>
using namespace std;
typedef long long ll;

int hd[100010],num;
struct node {
	int next,to;
	ll v;
} edg[200010];
inline void add(int fr,int to,ll v) {
	edg[++num].to=to;
	edg[num].v=v;
	edg[num].next=hd[fr];
	hd[fr]=num;
}

ll b[100];
inline void upd(ll x) {
    for(int i=60;~i;--i)
        if(x&1LL<<i)
            if(b[i]) x^=b[i];
            else {b[i]=x;break;}
}

ll d[50010];
bool vis[50010];
void DFS(int x) {
	vis[x]=1;
	for(int i=hd[x];i;i=edg[i].next) {
		int v=edg[i].to;
		if(vis[v]) upd(d[v]^edg[i].v^d[x]);
		else d[v]=d[x]^edg[i].v,DFS(v);
	}
}

int n,m;
int main () {
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i) {
		ll x,y,z;
		cin>>x>>y>>z;
		add(x,y,z),add(y,x,z);
	}
	DFS(1);
	ll ans=d[n];
	for(int i=60;~i;--i)
		if((ans^b[i])>ans) ans^=b[i];
	cout<<ans<<endl;
	return 0;
}

例五：[HAOI2017] 八纵八横

算法分析：线性基，图形结构，DFS，bitset。

参考例四的思路，只有环上边能对答案做出贡献。因此通过 DFS 找返祖边搜环，扔进线性基里去，找到最大值即可。

注意到含有删除操作。因此把操作离线掉，之前介绍的带删除线性基派上了用场。

另外一个需要注意的点是，经济影响因子的二进制最大长度为

10^3

，因此常规的线性基无法通过本题，需要改用 bitset。

据说有在线做法？srds 笔者太菜了不会。（悲

CPP

#include <bitset>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=1010;
typedef bitset<N> BT;

inline void in(BT &x) {
    string s;
    cin>>s;
    BT tmp(s);
    x=tmp;
}
inline void out(BT x) {
    bool flag=0;
    for(int i=999;i>=0;--i) {
        if(x[i]||flag) putchar('0'+x[i]);
        if(x[i]) flag=1;
    }
    if(!flag) putchar('0');
    putchar('\n');
}

int tot,hd[N];
struct node {
    int next,to;
    BT v;
} edg[N];
inline void add(int fr,int to,BT v) {
    edg[++tot].to=to;
    edg[tot].v=v;
    edg[tot].next=hd[fr];
    hd[fr]=tot;
}

BT p[N];
int t[N];
void upd(BT x,int time) {
    for(int i=1000;i>=0;--i)
        if(x[i]) {
            if(t[i]<time) swap(time,t[i]),swap(x,p[i]);
            if(time==0) break;
            x^=p[i];
        }
}
void getmx(int time) {
    BT ans;
    for(int i=1000;i>=0;--i)
        if(time<t[i]&&!ans[i]) ans^=p[i];
    out(ans);
}

BT dis[N];
bool vis[N];
void DFS(int x) {
    vis[x]=1;
    for(int i=hd[x];i;i=edg[i].next) {
        int v=edg[i].to;
        if(vis[v]) upd(dis[v]^edg[i].v^dis[x],0x3f3f3f3f);
        else dis[v]=dis[x]^edg[i].v,DFS(v);
    }
}

int n,m,q,qcnt,ed[N],op[N],del[N];
BT val[N];
pair<int,int>New[N];
int main () {
    ios::sync_with_stdio(0);
    cin>>n>>m>>q;
    int num=q+1;
    for(int i=1;i<=m;++i) {
        int u,v;
        BT w;
        cin>>u>>v,in(w);
        add(u,v,w),add(v,u,w);
    }
    DFS(1);
    for(int i=1;i<=q;++i) {
        string s;
        cin>>s;
        int x,y;
        BT z;
        if(s=="Add") {
            cin>>x>>y,in(z);
            op[i]=++qcnt;
            val[qcnt]=(z^dis[x]^dis[y]);
            New[qcnt]=make_pair(x,y);
            del[qcnt]=qcnt;
        }
        else if(s=="Change") {
            cin>>x,in(z);
            ed[del[x]]=i;
            op[i]=--num;
            val[num]=(z^dis[New[x].first]^dis[New[x].second]);
            del[x]=num;
        }
        else if(s=="Cancel") {
            cin>>x;
            ed[del[x]]=i;
        }
    }
    for(int i=1;i<=q;++i)
        if(!ed[i]) ed[i]=0x3f3f3f3f;
    getmx(0);
    for(int i=1;i<=q;++i) {
        if(op[i]) upd(val[op[i]],ed[op[i]]);
        getmx(i);
    }
    return 0;
}

9、线性基习题

限于篇幅，恕不赘述。

笔者找到了一个题单，里面的习题还是挺全的，就放在这里了。

10、结语

参考资料：

另外，感谢魏老师对本文的审核，并提出了意见。

由于笔者很菜，所以本文可能有一些不妥之处，请各路神犇看到后在评论区加以指正。

就此搁笔。希望你在阅读本文以后对线性基有所了解。

【学习笔记】浅谈异或线性基

文章操作

1、前言

2、线性基基本概念

3、线性基重要性质

性质一

性质二

性质三

性质二

性质一

性质三

4、线性基基本操作

插入

求最大值

求最小值

求 $k$ 小值

询问存在性

线性基求并

线性基求交

5、带删除线性基

插入

求最大值

6、线性基复杂度

时间复杂度

空间复杂度

7、线性基例题

例一：[BJWC2011]元素

例二：[TJOI2008]彩灯

8、线性基扩展应用

例三：[CQOI2013] 新 Nim 游戏

例四：[WC2011]最大 XOR 和路径

例五：[HAOI2017] 八纵八横

9、线性基习题

10、结语

相关推荐

评论

【学习笔记】浅谈异或线性基

文章操作

1、前言

2、线性基基本概念

3、线性基重要性质

性质一

性质二

性质三

性质二

性质一

性质三

4、线性基基本操作

插入

求最大值

求最小值

求 kkk 小值

询问存在性

线性基求并

线性基求交

5、带删除线性基

插入

求最大值

6、线性基复杂度

时间复杂度

空间复杂度

7、线性基例题

例一：[BJWC2011]元素

例二：[TJOI2008]彩灯

8、线性基扩展应用

例三：[CQOI2013] 新 Nim 游戏

例四：[WC2011]最大 XOR 和路径

例五：[HAOI2017] 八纵八横

9、线性基习题

10、结语

相关推荐

评论

求 $k$ 小值