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

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$ 插入到了线性基的第 $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 【模板】线性基](https://www.luogu.com.cn/problem/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（二者只能加入其一）加入答案的线性基中。

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

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 表示这个元素的最晚删除时间。

插入

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

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

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];
        }
}

求最大值

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

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

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。

#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。

#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 是没分的。

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

#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 树上通过返祖边找到简单环的方法，很容易能找到环。

#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 笔者太菜了不会。（悲

#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、结语

参考资料：

• 线性基详解

• 线性基求交与求并

• 男默女泪！线性基求交全网最通俗解释

• [WC2011] 最大XOR和路径 题解

• [HAOI2017] 八纵八横 题解

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

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

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