线性基

· · 个人记录

对于 n 个向量 a_1,a_2\cdots a_n，若存在 n 个数 b_1,b_2\cdots b_n 满足向量 x=b_1a_1+b_2a_2+\cdots+b_na_n，则 x 是 a_1,a_2\cdots a_n 的线性组合。

对于一个向量集合，若不存在一个向量是其他向量的线性组合，则这些向量线性无关，否则线性相关。一个向量集合对应的向量空间，是其中所有子集的线性组合组成的集合。显然向量空间满足其中任意子集的线性组合仍属于这个向量空间。一个向量空间的基就是极大线性无关子集，容易证明基的大小是固定的，等于这些向量组成的矩阵的秩。

如何求线性基？考虑高斯消元。从前到后依次加入每个向量，考虑之前的向量的一组基，满足这组基的向量组成的矩阵是阶梯型矩阵。新加入一个向量 a，从小到大枚举 j，若基中存在一个向量 c_i 满足第一个非零位是第 j 位，则用 c_i 把 a 的第 j 位消成零。否则将当前的 a 插入基。设向量维数为 m，则时间复杂度为 O(nm^2)。

OI 中的线性基通常是二进制的，即向量中每个元素均为 0/1。将某一位消成零时只需要异或上 c_i 即可。若 m\leq 64 则将向量压成一个整数，否则用 bitset 优化，时间复杂度 O(nm^2/w)。见 bitset 求解异或方程组。

模板题：#113. 最大异或和

首先求出这 n 个数的一组基，c_i 表示最高非零位为 i 的向量（不存在则为 0）。然后从高位到低位贪心，若当前答案 ans 的第 j 位为 0，则 ans\leftarrow ans\oplus c_j。

时间复杂度是构造基的复杂度，即 O(n\log s_i)。

提交记录

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll c[53];
int main(){ios::sync_with_stdio(0);cin.tie(0);
    int n,i,j;
    ll x;
    cin>>n;
    for(i=1;i<=n;++i){//构造基
        cin>>x;
        for(j=50;~j;--j)if(x>>j&1){
            if(!c[j]){c[j]=x;break;}//插入基
            x^=c[j];//将第j位消成0
        }
    }
    for(x=0,j=50;~j;--j)if(!(x>>j&1))x^=c[j];//求最大异或和
    cout<<x;
    return 0;
}

模板题 2：#114. k 大异或和

先求出一个线性基，然后对其进行一些改造，变成一个最简行阶梯矩阵。方法是从小到大枚举 i，若 c_i 不为 0，则从 i-1 开始从大到小枚举 j，若 c_i 的第 j 位为 1，则 c_i\leftarrow c_i\oplus c_j。

改造后的线性基有一个性质，就是假设 w 是若干个 c_j 异或得到的，其中 j>i，若 c_i>0，则 w<w\oplus c_i，因为最简行阶梯矩阵满足除 c_i 以外的数第 i 位都为 0，则 w 的第 i 位也为 0，而异或上 c_i 不会影响 i+1 以后的位。

求出 b_i 表示 c 中第 i 个非零元素（i 从零开始）。则第 k 小的异或和即为：将 k 转化为二进制数，所有为 1 的位 i 对应的 b_i 的异或和。

注意一种特殊情况，就是原集合 S 中存在线性相关的元素，则可以异或出 0，k\leftarrow k-1 即可。

时间复杂度 O((n+m)\log s_i)。

提交记录

例题：CF895C Square Subsets

能表示成整数的平方，意味着每个质因子的次数都是偶数。将每个数按每个质因子的次数奇偶性写成一个二进制数，第 i 位为 1 表示第 i+1 个质数的次数为奇数。所求即为异或和为 0 的非空子集个数。若共有 n 个数，线性基中有 t 个数，则另外 n-t 个数的任意一个子集的异或和，有且仅有一个基中 t 个数的子集的异或和与之相等，去掉空集以后方案数即为 2^{n-t}-1。

例题 2：CF724G Xor-matic Number of the Graph

异或线性基结合图论的简单题。异或有一个重要的性质，就是 x\oplus x=0，所以一条边走两遍贡献会抵消掉。考虑对每一个连通块，随便钦定一个根，求一棵生成树，记 d_x 为点 x 到根的路径边权异或和。每一条非树边 (u,v,w) 对应一个权值为 d_u\oplus d_v\oplus w 的环。任意两点 u,v 的路径，一定可以表示成 u 到 v 的树上路径，再加上任意个环。

将所有环的权值加入线性基，所求即为 \sum d_u\oplus d_v\oplus x，其中 x 为线性基的任意一个子集的异或和。记 w_{i,0/1} 表示异或和第 i 位为 0/1 的子集数量，可以通过 dp 求出，dp_{j,i,0/1} 表示只考虑线性基的前 j 个数的答案。线性基元素个数不超过边数，所以这部分复杂度是 O(m\log t_i)。然后枚举连通块内的点 x，求出 f_{i,0/1} 表示 x 以前的点 y 满足 d_y 的第 i 位为 0/1 的个数，设 x 的第 i 位为 b，则将 2^i\times (f_{i,b}\times w_{i,1}+f_{i,\neg b}\times w_{i,0}) 加入答案，这部分复杂度 O(n\log t_i)。总的复杂度即为 O((n+m)\log t_i)。

例题 3：CF1100F Ivan and Burgers

长度为 n 的数组，q 次询问区间最大异或和。

将询问按右端点排序，从小到大枚举右端点。设当前枚举到 i。考虑线性基求最大异或和的过程，也就是从高位到低位贪心。对于高位的元素 c_j，我们希望它对应原序列中的位置 p_j 尽可能大。考虑修改一下线性基插入的过程，从大到小枚举 j，设当前需要插入 x，对应原序列位置是 y，x 的第 j 位为 1，若 c_j=0，则 c_j\leftarrow x,p_j\leftarrow y。否则若 y>p_j，则交换 x,c_j，交换 y,p_j。然后 x\leftarrow x\oplus c_j，然后考虑下一位。这样可以保证高位的 p 尽可能大。

回答询问和一般的最大异或和相比，只需要多判断一下 l\leq p_j。时间复杂度 O((n+q)\log c_i)。

带删除线性基（离线）

暴力做法是用线段树分治，复杂度 O(n\log n\log v)。

更好的做法是，用例题 3 的做法，将删除的时间作为 p_i，维护 p_i 尽可能大的线性基即可。复杂度 O(n\log v)。

线性基合并

给定两个基，对应向量空间 V_1,V_2，求 V_1\cup V_2 对应的向量空间的基（注意 V_1\cup V_2 不一定是向量空间）。

将一个基的元素插入另一个基即可，单次合并复杂度 O(\log^2 v)。

例题：P4839 P哥的桶

在例题 3 的基础上增加了插入操作。

暴力做法：

用线段树维护区间线性基，修改时在 \log n 个线性基中插入，查询时合并区间对应的 \log n 个线性基，时间复杂度 O(n\log^2 v\log n)（假设 n,m 同阶）。

更好的做法：

离线。记每个数被插入的时间为 p，位置为 x，查询的时间为 t，则相当于求满足 p<t,l\leq x\leq r 的数的最大异或和。用例题 3 的方法，维护 p 尽可能小的线性基。现在就转化为静态的区间线性基问题。考虑猫树分治，建树的过程需要 O(n\log n) 次线性基插入，查询时需要一次线性基合并，复杂度即为 O(n\log v(\log n+\log v))。

线性基求交

参考博客

首先有一个显然的性质：向量空间的交还是向量空间。考虑两个向量空间 V_1,V_2 的交，对于 V_1\cap V_2 中的向量 a_1,a_2，根据向量空间的定义，a_1+a_2 一定属于 V_1 和 V_2，即属于 V_1\cap V_2。所以 V_1\cap V_2 是向量空间。

线性基求交，就是给定两个基，对应向量空间 V_1,V_2，求 V_1\cap V_2 的基。

引理：若 V_1,V_2 是线性空间，B_1,B_2 分别是它们的基，令 W=B_2\cap V_1，若 B_1\cup (B_2\setminus W) 线性无关，则 W 是 V_1\cap V_2 的一组基。

证明：根据 W 的定义有 W 中的元素线性无关，所以 W 是对应向量空间的基。根据 W 的定义，W 中的向量都能被 B_1 和 B_2 分别表示。因为 B_1\cup (B_2\setminus W) 线性无关，所以 B_2\setminus W 中的向量不能被 B_1 表示。所以 W 是 V_1\cap V_2 的一组基。

任取 B_1,B_2，有可能 B_1\cup (B_2\setminus W) 线性相关。这时需要构造一组 B_2' 满足 B_1\cup (B_2'\setminus W) 线性无关。

具体做法：

维护两个线性基数组，tmp 表示 B_1\cup (B_2\setminus W) 初始为 B_1，ans 表示 W 也就是答案初始为空，再维护一个数组 arr 初始等于 B_1。

从小到大加入 B_2 中的元素 x。

若 x 能被 tmp 表示，则 x 对应 ans 中的一个元素，但根据 W 的定义还需要满足 x\in V_1，考虑将 x 拆分为 S,T 的线性组合，其中 S\subset B_1,T\subset (B_2'\setminus W)，令 s=\oplus S_i，则在 ans 中加入 s。设 x 不为 0 的最高位为 i，因为当前 B_2'\setminus W 中的元素第 i 位一定为 0，所以 s 第 i 位一定为 1，可以直接令 ans_i=s。

若 x 不能被 tmp 表示，插入 tmp 即可。

用数组 arr 求 s，用 tmp_j 消元时 s\leftarrow s\oplus arr_j，将消元后的 x 插入 tmp_j 时令 arr_j=s。

时间复杂度 O(\log^2 v)。

using ll=unsigned long long;
struct B{
    ll c[65];
    B(){memset(c,0,520);}
    void ins(ll v){for(int i;v;v^=c[i])if(!c[i=__lg(v)]){c[i]=v;break;}}//插入
    B&operator&=(const B&b){//将*this和b合并结果存入*this
        B arr=*this,ans;//变量名含义见上文，此处*this表示tmp，注意arr不是线性基
        int i=0,j;
        ll v,s;
        for(;i<64;++i)if(v=b.c[i])for(s=0;v;){
            if(c[j=__lg(v)]){
                v^=c[j],s^=arr.c[j];
                if(v)continue;
                ans.c[i]=s;//v能被*this表示，向ans加入s
            }else c[j]=v,arr.c[j]=s;//v不能被*this表示，向*this加入当前的v，arr[j]等于当前的s
            break;
        }
        return*this=ans;
    }
};

例题：#698. 【候选队互测2022】枪打出头鸟 提交记录

首先求出 b_i 表示位置 i 的可重集的线性基，然后求出 pr_i 表示 b_1\cap b_2\cap\cdots\cap b_i，这部分复杂度 O((n\log v+\sum k)\log v)。

暴力做法：二分答案 i，判断 pr_i 能不能表示 x，询问复杂度 O(q\log n\log v)。

优化做法 1：注意到 pr_i 只会变化 \log v 次，只保留这 \log v 个不同的 pr_i，二分答案，复杂度 O(q\log \log v\log v)。

优化做法 2：记 p_i 为基的位置 i 为空的最小时间，初始为 n+1。用所有 c_i=pr_{{p_i-1},i} 构造一个新的基，在这个基中查询 x，异或 c_i 时 ans 和 p_i 取 \min 即可。复杂度 O(q\log v)。

带删除线性基（在线）

对于基中的向量 b_i（不在基中则 b_i 为 0），维护一个 bitset v_i 表示 b_i 是由哪些向量异或成的，若 v_{i,j}=1 则异或的向量包含 x_j。

考虑删除向量 x_i，找到一个 v_{j,i}=1 的 j 满足 b_j=0，若不存在 b_j=0 的 j 则找一个 b_j 的最高非零位最小的 j。将 b_j 删掉，然后对所有 k，若 v_{k,j}=1 则 v_k\leftarrow v_k\oplus v_j,b_k\leftarrow b_k\oplus b_j。因为 b_j 满足最高非零位最小，所以这样不会改变其他 b_k 的最高非零位。

设向量个数为 n，位数为 m，则删除复杂度为 O((n+m)n/w)。插入时需要维护 v，复杂度变为 O((n+m)m/w)。所以这种做法只适用于向量个数较小的题目。

例题：#453. 【集训队作业2018】围绕着我们的圆环

容易发现答案只与 C 的秩有关，因为对 C 做初等行变换时对 A 做相同变换，对 C 做列变换时对 B 做相同变换，A\times B=C 仍然成立。

令 C_i 表示 C 的列向量，A_i 表示 A 的列向量。因为 C_k 是由 A_j 异或成的系数为 B_{j,k}，所以 C_i 在 A_i 的向量空间中。固定 A,C 不变，且 C 满足 C_i 在 A_i 的向量空间中，则对于每个 C_k，C_k=(A_1A_2\cdots A_q)B_k 的解数即为 2^{q-x}，其中 x 为 A 的秩，B 的总方案数即为 2^{(q-x)s}。

枚举 A 的秩 x。设 C 的秩为 r。记 f_{i,j} 表示 p\times i 的秩为 j 的矩阵个数，g_{i,j} 表示 s\times i 的秩为 j 的矩阵个数。固定 A 不变，合法的 C 的每个列向量都可以用 A_i 的基表示，可以写成一个 s\times x 的秩为 r 的矩阵，方案数为 g_{x,r}。而 A 的方案数为 f_{q,x}，答案即为 (\sum_{r\leq x\leq \min(p,q)} f_{q,x}g_{x,r}2^{(q-x)s})/f_{s,r}，可以线性计算。f,g 可以 O(n^2) 递推预处理。

现在只需要维护 C 的秩，用带删除线性基即可，这部分复杂度 O(n^2m/w)。

例题 2：#91. 【集训队互测2015】最大异或和

记 span(S) 为向量集合 S 的向量空间，显然有 span(v_1,v_2\cdots v_n)=span(v_1,v_2-v_1\cdots v_n-v_{n-1})。

求序列 a 的差分 b，b_1=a_1，b_i=a_i\oplus a_{i-1}（i>1）。

询问操作变为求 b 的最大异或和。区间异或操作变为 b_x 和 b_{y+1} 单点异或 w。区间赋值操作变为 b_x 异或 a_x\oplus w，b_{y+1} 异或 a_y\oplus w，b_{x+1},b_{x+2}\cdots b_{y} 全部清空。区间清空的复杂度可以均摊掉，总复杂度即为 O((n+m)^2q/w)。