线性基入门 | Arahc's Home

简介

线性基是一个一般用于处理集合中异或相关的问题，其时间复杂度和空间复杂度都是 $\log a$ 级别， $a$ 为值域。

线性基最常用的做法是兹瓷以下三个操作：

向集合内插入一个数。
查询集合内若干数能异或得到的最大值。
查询一个数是否能被集合内若干数异或得到。

当然它还有很多副效果，比如还可以用来……

查询集合内若干数能异或得到的最小值。
查询集合内若干数能异或得到的第 $k$ 小值。
查询集合内若干数能异或得到的第 $k$ 大值。

等等，你可以尽情扩展，只要你能做到。

若无特殊注明，一个数的某一位默认为二进制下而非十进制下，没有特殊标明和特判就不考虑 $0$ 。

基本操作

维护一个集合，支持两种操作：

插入一个数。
查询集合内任意数异或和的最大值。
查询一个数是否能用集合内若干数的异或和表示。

$n\leq 10^6,0\leq a_i<2^{50}$ 。

线性基用数组实现，记为 $p$ ， $p_i$ 的最高位 $1$ 在第 $i$ 位。用线性基维护一个数组，我们只需要考虑能让原数组 $a$ 可以通过 $p$ 异或得到即可。

求线性基的时候，先考虑插入一个数 $x$ 。优先找到 $x$ 的 $1$ 的最高位（设为 $i$ ），如果线性基中没有对应的位，则把 $x$ 插入到线性基内，令 $p_i\leftarrow x$ 。

如果不是的时候，因为维护线性基需要满足 $p$ 的元素可以异或得到 $a$ 的元素，从插入一个数线性基的影响的角度看，如果插入的数已经可以被线性基中的元素表示了，还需要更新线性基吗？

所以，从 $x$ 完全对线性基没有贡献这一特性考虑，如果 $x=p_{k_1}\oplus p_{k_2}\oplus\cdots\oplus p_{k_m}$ ，线性基没有变化。

如果最高位 $i$ 已经有数字占用了，就令 $x\leftarrow x\oplus p_i$ ，然后继续考虑新的 $x$ 的最高位。因为 $p_i$ 的第 $i$ 位为 $1$ ， $x$ 的最高位为 $i$ ，所以更新后 $x$ 最高位小于 $i$ 。

如果一直更新 $x$ 直到 $x=0$ 了，都没有加入线性基，说明 $x$ 已经可以被线性基内元素异或得到了，无需插入。

按照这种方式插入，不难发现线性基内的数 $p$ 就可以表示原数组了，而且下标已经按照最高位排好序了，后续很多操作都会变得很方便。

不难发现线性基的数是无法异或出 $0$ 的，因此如果题目中可以有 $0$ ，需要特判一下。

找最大值则从大到小贪心，让高位尽量为 $1$ 。

这里提出的构造方法是不严谨的，它不满足一些线性基有的性质，对于有的题目如此构造将会无法用线性基解决，但是对于很多题目，这样直接构造即可。而且这种方法好写，写出 bug 率低。后文会指出线性基的线性代数意义和其用高斯消元构造的严谨构造法。

实现参考如下：

inline bool insert(int x){
    if(x==0){
        zero=1;
        return 1;
    }
    for(register int i=n;i>=0;--i)
        if(x&(1LL<<i)){
            if(!p[i]){ // 线性基内没有本元素
                ++cnt,p[i]=x; // 插入，cnt 维护线性基内元素个数
                return 1;
            }
            x^=p[i];
        }
    return 0; // 插入失败，原值已经可以被表示
}
inline int askmax(){// 从高到底贪心选让高位尽大
    int res=0;
    for(register int i=n;i>=0;--i)
        res=max(res,res^p[i]);
    return res;
}
inline bool askcan(int x){// 和插入差不多
    for(register int i=n;i>=0;--i)
        if(x&(1LL<<i)){
            if(!p[i])
                return 0;
            x^=p[i];
        }
    return x==0;
}
inline int askmin(){ // 最小值就是 p 的最小值
    if(zero) return 0;// 有 0 特判
    for(register int i=0;i<=n;++i) // 找最小值
        if(p[i])
            return p[i];
    return 0;
}

进阶操作

我们回头把线性基在线性代数上的意义过一下：

根据前面的方法，我们对线性基的认识是：通过原集合 $S$ 中的某一个最小子集 $S_1$ 组成，使得 $S_1$ 内元素相互异或得到的值域和 $S$ 得到的值域相同。

进一步，要把原集合的 $n$ 个数放在二进制下，看成 $n$ 个向量，每个向量的每个元素都是 $0$ 或 $1$ （即一个数的二进制位形成它代表的向量）。如果一些向量中任意一个向量能被其它向量通过异或运算得到，说明这些向量（在异或意义下）线性相关。线性基中所有的向量是线性无关的。

也就是说，线性基的线性代数意义应该是：一个向量集合的极小的线性无关子集，满足线性基中元素异或得到的值域和原向量集合相同（这里用到了基的性质，即可以表示出原空间内所有点，在这里空间内所有点表示的是原集合异或得到的值域）。

然后把基本的东西搞完，得到一个性质：线性基能异或出的每一个数的组成方案是唯一的。即对于任意两个不同的线性基能异或出来的数，异或出这两个数的方案一定不同且唯一。

因此设基内有 $cnt$ 个元素，那么其能表示的数有 $2^{cnt}-1$ 个。

维护一个集合，支持两种操作：

插入一个数。
查询集合内任意数异或和的第 $k$ 小。

$n\leq 10^4,a_i<2^{50}$ 。

我们发现线性基是按照每个二进制最高位是多少存数字的，是不是可以对 $k$ 二进制分解呢？

分解之后就可以直接二进制原理做了，但应该要保证 $p_i$ 的最高位是 $i$ ，而且 $p_i$ 要尽量小。

我们发现前面的构造方法是不能满足新加入的这个条件的。因此我们需要改进线性基的构造方法。

我们先假设原向量集合的基 $\mathfrak{B}$ 就是向量集合 $a$ ，原向量集合的张成为 $V$ ，进行如下操作：

若 $a_1 = 0$ ，在 $\mathfrak{B}$ 中去掉 $a_1$ 。
若 $a_j\in \rm{span}(a_1,\cdots,a_{j-1})$ ，其中 $j\in(1,n]$ ，在 $\mathfrak{B}$ 中去掉 $a_j$ 。

因为每次去掉的向量都属于其前面若干向量的张成，因此它和前面的相邻线性相关，去掉就保证了 $\mathfrak{B}$ 的元素线性无关。且最后 $\mathfrak{B}$ 一定可以张成 $V$ ，因此 $\mathfrak{B}$ 就是原向量集合的基。

高斯消元可以判断一个向量能否被其它向量张成。维护一个对角矩阵，考虑到 $a_i$ 时，从高到低枚举其为 $1$ 的位 $j$ 。若 $j$ 这一行对角处已经是 $1$ 则不能加入，需要把这一行的向量异或 $a_i$ ；若为 $0$ 则把 $a_i$ 加入。每加入数字的时候将其消元（维护三角性质），先用下面的数消自己，再用自己消上面的数。

不难发现除了对角的 $1$ ，别的 $1$ 能消就消，因此这样的构造方式就满足了 $p_i$ 尽量小的条件。

举个例子，维护五个数的线性基 $a=\left\langle (111)_2, (001)_2, (100)_2, (011)_2, (101)_2 \right\rangle$ ：

\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}

$a_1\neq 0$ ，最高位为 $1$ ，插入到第一行：

\begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}

$a_2$ 不能被 $a_1$ 张成，最高位在第三位：

\begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}

我们需要维护对角矩阵，用下面的数消掉上面的数，当然第一行第二列的 $1$ 消不掉，没关系不管它：

\begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}

$a_3$ 最高位在第一位，但是最高位已经有数了，让它与第一行的数 $(110)_2$ 异或一下变成 $(010)_2$ 。最高位在第二位：

\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

这个 $1$ 不能消掉下面的数字，但是能消掉上面的数字：

\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

现在的对角矩阵已经完全形成了，其他数必然无法再加入。

这样选择进来的 $a_1,a_2,a_3$ 就是 $V$ 的一个基 $\mathfrak{B}$ 。只不过我们还进行了高斯消元变换得到了这个矩阵。众所周知初等行变换不影响线性无关性，且初等行变换后这些向量仍然能张成原有的向量空间。

矩阵里的数 $p_1=4,p_2=2,p_3=1$ ，也是原向量空间的的一个基。最后线性基 $\mathfrak{B}$ 就取这个矩阵的数 $p$ 即可。

至于异或第 $k$ 大，按照消元法求出一组线性基，将 $k$ 二进制拆分，从低到高分别为 $a_1,a_2,\cdots,a_x$ ，答案为：

a_1\cdot p_1 \oplus a_2\cdot p_2 \oplus \cdots \oplus a_x\cdot p_x

因为这样构造后，记 $p_i$ 为 $\mathfrak{B}$ 中最高二进制为 $i$ 的数， $p_i\oplus p_j$ 在第 $j$ 位及其更低的位的部分的数已经到达理论最小值，结合二进制原理， $p_i\oplus p_j$ 是第 $2^{i-1}+2^{j-1}$ 大异或和。

inline void build(int *a,int m){// 构造 a 的线性基，a 大小为 m
    for(register int i=1;i<=m;++i)
        for(register int j=n;j>=0;--j)
            if(a[i]&(1LL<<j)){
                if(!p[j]){
                    p[j]=a[i];
                    for(register int k=j-1;k>=0;--k) // 先下面消这一行
                        if(p[j]&(1LL<<k))
                            p[j]^=p[k];
                    for(register int k=j+1;k<=n;++k) // 再这一行消上面
                        if(p[k]&(1LL<<j))
                            p[k]^=p[j];
                    break;
                }
                a[i]^=p[j];
            }
}
inline int getkmin(int k){
    if(zero) --k; // 特判 0
    int res=0,x=0,tmp=k;
    while(tmp){
        d[++x]=(tmp&1LL); // 求 k 的二进制拆分
        tmp>>=1;
    }
    for(register int i=0,j=1;i<=n && j<=x;++i)
        if(p[i]){
            res^=p[i]*d[j];
            ++j;
        }
    return res;
}

例题

Luogu3857 彩灯

有一个初始为 $0$ 的变量 $a$ ，给定 $n$ 个数，可以选任意多个数去异或 $a$ ，求 $a$ 可以得到多少不同的值。

$n\leq 50,x_i< 2^{50}$ 。

题解

根据前面的得到的性质，再加上不选择任何数的 $0$ ，答案为 $2^{cnt}$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=55,max_s=55,mod=2008;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int reads(){
	int x=0;char c=getchar();
	while(c!='O' && c!='X') c=getchar();
	while(c=='O' || c=='X') x=(x<<1)+(c=='O'),c=getchar();
	return x;
}
inline int mi(int a,int p){
	int res=1;
	while(p){
		if(p&1) res*=a,res%=mod;
		a*=a,a%=mod,p>>=1;
	}
	return res%mod;
}

int n,m;

struct LB{
	int p[max_s],n,cnt;
	LB(){cnt=0;}
	inline void init(int x){
		n=x;
		memset(p,0,sizeof(p));
	}
	inline void insert(int x){
		for(register int i=n;i>=0;--i)
			if(x&(1LL<<i)){
				if(!p[i]){
					p[i]=x,++cnt;
					return;
				}
				x^=p[i];
			}
	}
	inline int getnum(){
		return cnt;
	}
}lb;

signed main(){
	n=read(),m=read(),lb.init(51);
	for(register int i=1;i<=m;++i){
		int x=reads();
		lb.insert(x);
	}
	write(mi(2,lb.getnum()));
	return 0;
}

Luogu4301 新 Nim 游戏

$n$ 堆石子，先手先取走任意整数堆石子，后手再取走任意整数堆石子。然后按照 Nim 游戏进行。求先手必胜时最少拿走多少堆石子。

$n\leq 100,a_i\leq 10^9$ 。

题解

先手需要胜利，意味着后手无论拿掉多少堆都无法得到异或和为 $0$ 的情况。

考虑我们用朴素方法插入线性基的时候，如果没有成功插入，意味着插入的数可以表示为线性基内的数异或的情况，如果加上这个数的话，那么就存在了这样的异或和为 $0$ 的情况。

因此我们只需要保证加入的时候这个数能成功插入线性基即可，如果不能插入，说明先手一定要把这堆石子取走。

注意到我们还需要让先手取走的石子数最小，考虑贪心，从大到小尝试，能插入就插入，否则取走。因为异或是不进位加法，所以若干个数的异或和小于等于这些数的和，因此取走这个多余的数一定比保留这个数，取走别的数更优。因此如果一个位置可以放小数字也可以放大数字，放大数字的方案相比放小数字的答案是不劣的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=102,max_s=35;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline bool cmp(int a,int b){
	return a>b;
}

int n,a[max_n],ans;

struct LB{
	int p[max_s],n,cnt;
	inline void init(int x){
		n=x,cnt=0;
		memset(p,0,sizeof(p));
	}
	inline bool insert(int x){
		for(register int i=n;i>=0;--i)
			if(x&(1LL<<i)){
				if(!p[i]){
					++cnt,p[i]=x;
					return 1;
				}
				x^=p[i];
			}
		return 0;
	}
}lb;

signed main(){
	n=read(),lb.init(33);
	for(register int i=1;i<=n;++i)
		a[i]=read();
	sort(a+1,a+1+n,cmp);
	for(register int i=1;i<=n;++i)
		if(!lb.insert(a[i]))
			ans+=a[i];
	write(ans);
	return 0;
}

Luogu4151 最大 XOR 和路径

给定一个 $n$ 点 $m$ 边的带权无向图，你需要找到一条 $1$ 到 $n$ 的路径（可以不是简单路径），使边权异或和最大。输出这个最大值。

$n\leq 5\times 10^4,m\leq 10^5,w_i\leq10^{18}$ 。

题解

任意一条路径异或和都可以由一条简单路径异或和以及若干环的异或和得到。且这些环不一定要在简单路径的点上，因为我可以到这个环，走一圈再原路返回出发点，去环的这条路的边权被异或了两次，直接抵消。

因此我们需要找出所有的环，然后把环的异或值用线性基维护起来，然后随便找一条简单路径，记这个简单路径的边权异或和为 $s$ 。现在的问题转化为：在集合内选出一个若干数的异或和，使得这个异或和与 $s$ 异或起来最大。

用消元法构造出这个线性基，只需从大到小依次考虑选择这个线性基向量能否使异或值最大即可。

证明则设当前答案为 $s$ ，考虑到第 $k$ 位，对应线性基内的向量为 $\vec{v}$ ：

如果 $\vec{v}$ 的第 $k$ 位为 $0$ ，选不选无所谓。
若 $s,\vec{v}$ 的第 $k$ 位为 $1$ ，则异或使答案更小，实际上也没有选，成立。
若 $s,\vec{v}$ 的第 $k$ 位为 $0,1$ ，则异或使答案更大，实际上也选了，成立。

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=100005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(!isdigit(c)) w|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct Graph{
    int ct,hd[max_n],to[max_n<<1],ln[max_n<<1],nx[max_n<<1];
    Graph(){ct=1;}
    inline void add(int u,int v,int w){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
    }
    inline void add2(int u,int v,int w){
        add(u,v,w),add(v,u,w);
    }
}e;

int n,m;

struct LinerBasis{
    int p[77],n;
    inline void init(int x){
        n=x;
        memset(p,0,sizeof(p));
    }
    inline void insert(int x){
        for(int i=n;i>=0;--i) if((x>>i)&1){
            if(!p[i]){
                p[i]=x;
                return;
            }
            x^=p[i];
        }
    }
    inline int askmax(int x){
        int res=x;
        for(int i=n;i>=0;--i) if((res^p[i])>res)
            res^=p[i];
        return res;
    }
}lb;

int f[max_n];
bool vis[max_n];

inline void dfs(int u){
    vis[u]=1;
    for(int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(vis[v]){
            lb.insert(f[u]^f[v]^e.ln[i]);
            continue;
        }
        f[v]=f[u]^e.ln[i];
        dfs(v);
    }
}

bool End;
#define File ""
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        e.add2(u,v,w);
    }
    lb.init(63);
    dfs(1);
    write(lb.askmax(f[n]));
    return 0;
}

CF1100F Ivan and Burgers

多次查询区间中的数的异或最大值。

$n,q\leq 5\times 10^5,a_i\leq 10^6$ 。

题解

考虑线性基内求异或最大值的时候，是从高到低贪心，如果异或这一位使答案更大就可以异或。

那么我们动态地维护一个数组 $pos_i$ 表示区间内使第 $i$ 位有值的数字是哪个下标传过来的。有多个下标的时候怎么办？把询问离线下来，按右端点小到大排序，这样就只需要维护下标中最大的即可。

查询答案的时候，先判断使这一位有值的最大的下标在这个区间内，因为是按照右端点排序的，不妨扫到一个右端点把这个值再插入到线性基内，这样判断是否在区间内就可以转化为查询 $pos$ 是否在这个区间的左端点右边。如果在区间内，再按照原本的方法更新答案即可。

这个题可以强制在线。我们提前把所有 $r$ 的结果预处理下来就可以直接查询了。

#include<bits/stdc++.h>
using namespace std;
const int max_n=500005,max_s=25;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}

int n,m,a[max_n];

struct que{
	int id,l,r;
	inline void init(int x,int y,int i){
		id=i,l=x,r=y;
	}
}q[max_n];

inline bool cmp(que a,que b){
	return a.r<b.r;
}

struct LB{
	int p[max_s],pos[max_n],n;
	inline void init(int x){
		n=x,
		memset(p,0,sizeof(p));
	}
	inline void insert(int x,int id){
		for(register int i=n;i>=0;--i)
			if(x&(1<<i)){
				if(!p[i]){
					pos[i]=id,
					p[i]=x;
					return;
				}
				if(pos[i]<id){
					pos[i]^=id^=pos[i]^=id,
					x^=p[i]^=x^=p[i];
				}
				x^=p[i];
			}
	}
	inline int getmax(int id){
		int res=0;
		for(register int i=n;i>=0;--i)
			if(pos[i]>=id)
				res=max(res,res^p[i]);
		return res;
	}
}lb;

int ans[max_n];

signed main(){
	n=read(),lb.init(21);
	for(register int i=1;i<=n;++i)
		a[i]=read();
	m=read();
	for(register int i=1;i<=m;++i){
		int l=read(),r=read();
		q[i].init(l,r,i);
	}
	sort(q+1,q+1+m,cmp);
	for(register int i=1,j=1;i<=n && j<=m;++i){
		lb.insert(a[i],i);
		while(q[j].r==i){
			ans[q[j].id]=lb.getmax(q[j].l);
			++j;
		}
	}
	for(register int i=1;i<=m;++i)
		write(ans[i]),putchar('\n');
	return 0;
}