线性基

Published: by Creative Commons Licence

  • Tags:

线形基

给定一组Zm2上的向量v1,…,vn。线性基可以用于找到由这些向量张开的线性子空间。其通过寻找向量组中的极大无关向量组来实现。

线性基的具体的实现方式类似于高斯消元，但是可以支持在线插入新的向量。每次插入操作的时间复杂度都是O(m2)，我们可以用bitset进行优化，可以达到O(m2/64)。

问题1：给定一组数A={a1,a2,…,an}，判断通过异或操作可以得到多少不同的数。

用这组数构建线性基，记r为线性基的大小，每个数都可以表示为线性基中若干个数的异或和，因此结果为2r。

问题2：给定一组数A={a1,a2,…,an}，判断其中有多少个子集，其异或和为0。

用这组数构建线性基，记r为线性基的大小。所有线性基的非空子集的异或和都必定非0，因此所有异或和为0的子集必定包含不属于线性基中的向量。事实上，我们考虑任意非线性基中向量的子集S，记其异或和为x，我们必定能找到线性基的某个子集T使得其异或和为x，这样我们就能确定一个异或和为0的子集S∪T。因此所有子集中异或和为0的子集共有2n−r个。

问题3：给定一组数A={a1,a2,…,an}，判断其中有多少个子集，其异或和为x。

假设有两个子集A和B的亦或和均为x，那么X⊕Y=0，这意味着B可以通过向集合X中加入X⊕Y即可得到Y，这边集合的亦或操作是指删除已有的，加入未有的元素。

因此我们需要做的就是建立一个线性基，之后尝试找到线性基的一个子集，令其亦或和为x。如果不存在这样的子集，那么就无解。否则设该子集为X，设r为线性基的大小，我们知道A中共有2n−r个子集的亦或和为0，我们用这些子集和X做亦或操作可以得到所有亦或和为x的所有子集，因此可以直接确定亦或和为x的子集数目为2n−r。

问题4：给定一组数A={a1,a2,…,an}，问可以切分为最多多少个连续的子序列，要要求任意多个（至少一个）子序列的亦或和都不为0。

首先所有数亦或和一定不能为0，否则无解。

首先计算所有亦或前缀和，得到新的序列B=b1,b2,…,bn，其中bi=a1⊕a2⊕…⊕ai。那么A序列中任意子序列的亦或和都可以表示为B序列中两个数的亦或和。考虑一个子序列划分，子序列的亦或和线性无关，假设子序列的结尾下标分别为i1,i2,…,ik。那么如果我们建立线性基，将bi1,bi1⊕bi2,…,bik−1⊕bik放入其中，由线性基的性质知道，我们可以等价将bi1,bi2,…,bik放入而不会影响结果。

因此问题变成，从B序列中选择一个子集（bn必须选择），使得它们线性无关。我们可以先将bn加入线性基，之后随便按什么顺序加入其它元素，最后线性基的大小就是所要的结果。

提供一个例题。

问题5：给定一颗有n个顶点的树，每个顶点上都写了一个数字。对于每个顶点，回答在以该顶点为根的子树中，任意选取顶点上的数字，有多少种不同的亦或和

这个问题实际上问的是线性基合并，某个集合上的线性基，可以通过亦或得到这个集合上的所有数值。而两个集合的线性基合并后，可以通过亦或得到这两个集合上所有的数值。

问题6：给定一组数A={a1,a2,…,an}，之后q次修改操作，每次操作给定两个下标i,j，要求交换ai和aj。每次操作后问可以切分为最多多少个连续的子序列，要求任意多个（至少一个）子序列的亦或和都不为0。

这个问题是问题4的强化版本，我们接下来证明交换操作不会影响最终结果。

问题4中将问题转换为从B序列得到线性基。现在考虑交换带来的影响，我们只需要证明在交换i和j=i+1时不会影响结果即可，因为任意交互都可以通过若干次相邻交换得到。

考虑交换带来的影响，只有1个数发生了变化$b'i=a{i+1}\oplus b_{i-1}。而其它数都没有变化。而b'i和b{i+1}构成的线性基与b_i和b_{i+1}$构成的线性基相同，因此结果不变。

问题7：给定一个A={a1,a2,…,an}，提供q个请求，请求分两类，查询请求和修改请求。修改请求修改某个ai的值。查询请求由三个数确定l,r,x，从al,al+1,…,ar中选取任意个数，将这些数的亦或和再亦或上x后得到结果，问最大的结果是多少。其中n,q≤10000，ai≤220

这个问题是询问区间元素上的线性基。由于线性基支持O((log2MAX)2)的时间复杂度的合并操作，因此我们可以把区间上的线性基放到线段树上维护，这样总的时间复杂度为O((n+q)(log2MAX)3)。

问题8：给定一个A={a1,a2,…,an}，提供q个请求，请求由三个数确定l,r,x，从al,al+1,…,ar中选取任意个数，将这些数的亦或和再亦或上x后得到结果，问最大的结果是多少。其中n,q≤500000，ai≤220

类似问题7，但是不支持修改，n和q大了很多。

我们需要注意到线性基具有一个性质。考虑后缀ai+1,ai+2,…,an，如果我们贪心构建线性基，且被加入的数为ai1,ai2,…,aik。那么在考虑后缀ai,ai+1,ai+2,…,an，贪心构建线性基，会被加入的数仅可能为ai,ai1,ai2,…,aik的子集。因此我们可以在处理完以下标i+1开始的后缀后，记录下加入到线性基中的数的下标。之后在处理以ai开始的后缀时，就可以复用这部分信息，在O((log2MAX)2)的时间复杂度内完成构建。

于是我们可以在O(n(log2MAX)2)的时间复杂度内得到所有连续子序列的线性基，在计算线性基的同时离线处理一下请求即可。总的时间复杂度为O(n(log2MAX)2+qlog2MAX)。

这题在CF上有一道例题。

问题9：给定n个数a1,a2,…,an，考虑所有n2个二元组(ai,aj)，其亦或和为ai⊕aj，我们将这些二元组的异或和按照从小到大排序后，问第k大的值为？其中n≤106

我们可以将ai放到前缀树上进行维护。同时维护多个指针，表示可能的两个元素对应的区间。这样我们就可以通过二分询问有多少个数对的亦或和大于等于x来得出第k大的值，考虑到在前缀树上的遍历实际上已经帮我们完成了二分的过程，因此只需要遍历前缀树即可。

这里有一个特殊的点就是前缀树可能会占用过大的空间，我们可以用排序后的数组来代替前缀树。（数组的区间对应某个前缀树顶点，区间中第i位为1的处于右孩子中，为0的处于左孩子中）

问题10：给定一颗拥有n个顶点的树，树上每条边都有自己的权重，对于树上所有n2顶点对(u,v)，我们记f(u,v)为从u到v的唯一路径上的所有边的权重的亦或和，将这些路径异或和从小到大排序后，问第k大的亦或和是多少，其中n≤106,1≤k≤n2

首先我们需要将路径的异或和转换为路径两个端点的权重的异或和。方法记录每个顶点的权重为从该顶点到根的路径上所有边的权重的异或和。

现在问题变成了问题9。

这里有一道题目。

问题11：给定N个数A1,…,AN和B1,…,BN以及M，要求选择一个下标集合I，满足⊕i∈IAi≤M的前提下，计算最大的⊕i∈IBi。其中0≤Ai,Bi,K≤1018，1≤N≤106。

一道题目。

记H=⌈logmaxi,jAi,Bj⌉

首先对于任意i≠j，我们可以将Ai和Bi分别替换为Ai⊕Aj和Bi⊕Bj，这不会影响我们问题的答案。

因此我们可以找到一组A上的最大线性无关基底，下标集合记作LA。将N−I下标的值，我们可以利用LA中的元素将他们的A属性消除为0，而这时候它们的成本为0，因此它们的B值可以被任意选择，我们将它们的B属性建立一个线性基X。

通过类似的方式可以保证LA中所有下标的A属性最高位都互不相同，我们可以从按最高位的大小从大到小暴力枚举LA中的所有元素是否出现在结果中，利用剪枝和预处理我们可以保证最多只会有2H种可能的情况需要考虑。

因此总的时间复杂度为O(NH+H2)。这里默认使用了位运算来避免操作单个位。

环、奇环、偶环

考虑Zm2的向量a1,a2,…,an，如果有a1+a2+…+an=x，那么我们称这些元素形成了一个x环。如果环的大小为奇数，则称为奇x环，否则称为偶x环。

对于向量组，是否有x环，等价于向量组张开的子空间中是否包含x。

可以发现如果向量a1,a2,…,an有奇x环，当且仅当向量都加上v后，新的向量组有奇x+v环。

一种简单的判断奇x环的方式是，取由向量组张成的子空间外的任意一个向量v，之后将所有向量都加上v+x。原向量组中有奇x环当且仅当新的向量组包含v环。实际上，要得到v环，至少需要使用奇数个向量（偶数个向量的和，加上v+x是不发挥作用的），而如果奇数个新向量的和为v，则意味着原来的这奇数个向量的和为x。

之后考虑如何判断偶x环的存在。取由向量组张成的子空间外的任意一个向量v，之后将所有向量都加上v+x。如果存在偶x环，那么新的向量组中一定依旧包含x环。并且如果新向量组存在x环，可以保证这一定是偶环，因为如果是奇环的话，会推出原向量组中存在v环，这是不可能的。

可以发现奇环的特点是在所有向量都加上v后会偏移v，而偶环的特点是不动。记所有向量加上向量v之前的线性基为A，加入后位B，那么所有偶环都落在A和B的交上，而所有奇环都落在B对A的差上（最后还得减去v）。

区间操作+线性基

线性基与区间操作的结合比较容易。

如果有单点修改操作，需要将线性基丢到线段树上维护，这样每次操作上推的时间复杂度为O(m3/64)，一次线段树操作涉及log2n次上推，因此每次操作时间复杂度高达O((m3/64)log2n)，很慢。

如果有区间修改操作。我们可以计算差量数组后转成单点问题。对于给定向量a1,…,an，得到的差分量bi=ai−ai−1，其中认为a0=0。此时可以证明al,bl+1,…,br张成的线性子空间与al,al+1,…,ar张成的线性子空间相同。对于不同的区间操作可以采用不同的策略：

  • 区间赋值操作，实际上等价于bl,br+1修改，bl+1,…,br全部清0。
  • 区间加法操作，等价于bl,br+1修改，其余元素不变。
  • 区间查询操作，查出bl+1,…,br组成的线性子空间后把al插入即可。

提供一道题目。

题目1：给定n个元素a1,…,an，以及m个查询，第i个查询要求判断是否存在一个ali,…,ari的子集，其异或和正好等于xi。其中1≤n,m≤106，且0≤ai<260。

提供一道题目。

我们可以在基础的线性基上加上一个过期时间的概念。假设当前的基为B，当插入一个新元素e时，如果这个元素不存在之前，那么新的基为B+e。否则必定存在B的某个子集b，使得子集中所有元素的异或和等于e。这时候类似于我们用LCT维护动态最小生成树的方式，我们选择一个在e之前过期的b中元素t进行替代（如果有多个，则选择最早过期的）。这时候最新的基为B−t+e。接下来我们考虑如何处理询问某个元素是否在基中。

接下来在时间点y的时候判断x是否处于B张开的空间中。我们只需要找出异或和为x的子集b中最早过期的元素，判断它是否在y或之前过期。

回到问题，当我们有这样一个数据结构的时候，我们只需要维护一个带过期时间的线性基。之后我们离线请求。之后我们将前面提到的将ai的过期时间设置为i+1。我们按照i的顺序插入ai。当插入ai后我们回答所有右边界为i的请求，即判断线性基在时间l的时候是包含元素x。

时间复杂度为O((n+m)log2M)。

线性基与线性子空间的双射关系

给定线性基B，可以唯一的确定其展开的子空间S。但是一般给定子空间，是不能唯一确定线性基的。因为同一个子空间中可能有多个线性基。

考虑给定子空间，确定其中的一组线性基。我们可以先找到其中一组最大线性无关组，之后进行高斯消元，将矩阵化成上三角形，且满足每个向量的最高位的1是唯一的，换言之如果向量x的最高位为第k位，则其余向量的第k位全为0。这是很容易做到的。

之后考虑这种形式的线性基的特点，我们将线性基中所有向量按照最高位出现的位置进行排序，分别记作x(1),x(2),…,x(t)。这时候可以发现张开的子空间（我们把0视作第0小的）中第1小的元素为x(1)，第二小的为x(2)，之后是x(1)+x(2)。可以发现这很类似于二进制进位的规则。因此第k小的向量为∑ti=1[ki=1]x(i)，其中ki表示k的二进制第i位。如果两个线性基张开的子空间相同，则基中最小的向量一定相同，第2i小的向量也一定相同，因此所有向量都一一匹配。这时候可以发现线性基和子空间存在一个双射关系，其中线性基中第i小的元素为线性子空间中第2i小的向量。

题目1：给定所有小于等于k的数，它们组成的线性空间中存在多少个不同的线性子空间。其中1≤k<260，结果对素数p取模。

提供一道问题。

我们可以通过上面提到的高斯消元法，利用线性基和线性子空间的一一对应关系，枚举线性基来枚举线性子空间。

做法类似于数位dp，记dp(i,j,ceil)表示前i个二进制，前j个线性基，ceil=1表示最大值正好等于k。这样时间复杂度和空间复杂度都是O(2×602)。

题目2：给定n个数a1,…,an，要求计算它们所有非空子集异或和中第k大的元素。

提供一道题目。

上面的高斯消元法得到的线性基x1,…,xt，答案为∑ti=1[ki=1]x(i)。

线性基下的最大最小运算

给定一个线性基L，把它消成上三角矩阵后，记Li表示最高二进制为第i位的向量，它可能不存在。L张开的线性子空间为V。

接下来记:

  • M(x)=max{y⊕x|y∈V}
  • m(x)=min{y⊕x|y∈V}

下面我们证明它们满足如下运算规则：

  1. M(x)⊕M(y)=m(x⊕y)
  2. m(x)⊕m(y)=m(x⊕y)
  3. M(x)⊕m(y)=M(x⊕y)

先证明第一条：

考虑M(x)=x⊕X，M(y)=y⊕Y，m(x⊕y)=x⊕X⊕y⊕Y′。其中X,Y,Y′∈V。

通过反证法，假设二者不同，记k是M(x)⊕M(y)与m(x⊕y)不同的位中最高的一位，此时一定有前者为1，后者为0（根据m运算的定义），且Y与Y′第k位不同。那么Y和Y′除了后k位可能不同以外，其它位应该完全相同。由于Y和Y′的第k位不同，因此可以断定x⊕X的第k位一定为1（否则这时候Lk不存在，那么Y和Y′的第k位由更高位所决定，而它们更高位完全一致，因此它们的第k位应该也完全相同）。这时候Y⊕y的第k位是0，而Y⊕y′的第k位为1，这时候有M(Y)=Y⊕y<Y⊕y′，这与M的定义相悖。因此假设不成立。

之后考虑第二条（证明类似）：

考虑m(x)=x⊕X，m(y)=y⊕Y，m(x⊕y)=x⊕X⊕y⊕Y′。其中X,Y,Y′∈V。

通过反证法，假设二者不同，记k是m(x)⊕m(y)与m(x⊕y)不同的位中最高的一位，此时一定有前者为1，后者为0（根据m运算的定义），且Y与Y′第k位不同。那么Y和Y′除了后k位可能不同以外，其它位应该完全相同。由于Y和Y′的第k位不同，因此可以断定x⊕X的第k位一定为0（否则这时候Lk不存在，那么Y和Y′的第k位由更高位所决定，而它们更高位完全一致，因此它们的第k位应该也完全相同）。这时候Y⊕y的第k位是1，而Y⊕y′的第k位为0，这时候有m(Y)=Y⊕y>Y⊕y′，这与m的定义相悖。因此假设不成立。

之后考虑证明第三条（证明类似）：

考虑M(x)=x⊕X，m(y)=y⊕Y，M(x⊕y)=x⊕X⊕y⊕Y′。其中X,Y,Y′∈V。

通过反证法，假设二者不同，记k是M(x)⊕m(y)与M(x⊕y)不同的位中最高的一位，此时一定有前者为0，后者为1（根据M运算的定义），且Y与Y′第k位不同。那么Y和Y′除了后k位可能不同以外，其它位应该完全相同。由于Y和Y′的第k位不同，因此可以断定x⊕X的第k位一定为1（否则这时候Lk不存在，那么Y和Y′的第k位由更高位所决定，而它们更高位完全一致，因此它们的第k位应该也完全相同）。这时候Y⊕y的第k位是1，而Y⊕y′的第k位为0，这时候有m(Y)=Y⊕y>Y⊕y′，这与m的定义相悖。因此假设不成立。

提供几道用到这个结论的题目：