线性基

Published: by Creative Commons Licence

  • Tags:

线形基

给定一组$\mathbb{Z}_2^m$上的向量$v_1,\ldots,v_n$。线性基可以用于找到由这些向量张开的线性子空间。其通过寻找向量组中的极大无关向量组来实现。

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

问题1:给定一组数$A=\left\{a_1,a_2,\ldots,a_n\right\}$,判断通过异或操作可以得到多少不同的数。

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

问题2:给定一组数$A=\left\{a_1,a_2,\ldots,a_n\right\}$,判断其中有多少个子集,其异或和为0。

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

问题3:给定一组数$A=\left\{a_1,a_2,\ldots,a_n\right\}$,判断其中有多少个子集,其异或和为$x$。

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

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

问题4:给定一组数$A=\left\{a_1,a_2,\ldots,a_n\right\}$,问可以切分为最多多少个连续的子序列,要要求任意多个(至少一个)子序列的亦或和都不为0。

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

首先计算所有亦或前缀和,得到新的序列$B=b_1,b_2,\ldots, b_n$,其中$b_i=a_1\oplus a_2\oplus \ldots \oplus a_i$。那么$A$序列中任意子序列的亦或和都可以表示为$B$序列中两个数的亦或和。考虑一个子序列划分,子序列的亦或和线性无关,假设子序列的结尾下标分别为$i_1,i_2,\ldots, i_k$。那么如果我们建立线性基,将$b_{i_1},b_{i_1}\oplus b_{i_2}, \ldots, b_{i_{k-1}}\oplus b_{i_k}$放入其中,由线性基的性质知道,我们可以等价将$b_{i_1},b_{i_2},\ldots, b_{i_k}$放入而不会影响结果。

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

提供一个例题

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

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

问题6:给定一组数$A=\left\{a_1,a_2,\ldots,a_n\right\}$,之后q次修改操作,每次操作给定两个下标$i$,$j$,要求交换$a_i$和$a_j$。每次操作后问可以切分为最多多少个连续的子序列,要求任意多个(至少一个)子序列的亦或和都不为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=\left\{a_1,a_2,\ldots, a_n\right\}$,提供$q$个请求,请求分两类,查询请求和修改请求。修改请求修改某个$a_i$的值。查询请求由三个数确定$l,r,x$,从$a_l,a_{l+1},\ldots, a_r$中选取任意个数,将这些数的亦或和再亦或上$x$后得到结果,问最大的结果是多少。其中$n,q\leq 10000$,$a_i\leq 2^{20}$

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

问题8:给定一个$A=\left\{a_1,a_2,\ldots, a_n\right\}$,提供$q$个请求,请求由三个数确定$l,r,x$,从$a_l,a_{l+1},\ldots, a_r$中选取任意个数,将这些数的亦或和再亦或上$x$后得到结果,问最大的结果是多少。其中$n,q\leq 500000$,$a_i\leq 2^{20}$

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

我们需要注意到线性基具有一个性质。考虑后缀$a_{i+1},a_{i+2},\ldots, a_n$,如果我们贪心构建线性基,且被加入的数为$a_{i_1},a_{i_2},\ldots, a_{i_k}$。那么在考虑后缀$a_i,a_{i+1},a_{i+2},\ldots, a_n$,贪心构建线性基,会被加入的数仅可能为$a_i,a_{i_1},a_{i_2},\ldots, a_{i_k}$的子集。因此我们可以在处理完以下标$i+1$开始的后缀后,记录下加入到线性基中的数的下标。之后在处理以$a_i$开始的后缀时,就可以复用这部分信息,在$O((\log_2MAX)^2)$的时间复杂度内完成构建。

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

这题在CF上有一道例题

问题9:给定$n$个数$a_1,a_2,\ldots, a_n$,考虑所有$n^2$个二元组$(a_i,a_j)$,其亦或和为$a_i\oplus a_j$,我们将这些二元组的异或和按照从小到大排序后,问第k大的值为?其中$n\leq 10^6$

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

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

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

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

现在问题变成了问题9。

这里有一道题目

环、奇环、偶环

考虑$\mathbb{Z}_2^m$的向量$a_1,a_2,\ldots,a_n$,如果有$a_1+a_2+\ldots+a_n=x$,那么我们称这些元素形成了一个$x$环。如果环的大小为奇数,则称为奇$x$环,否则称为偶$x$环。

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

可以发现如果向量$a_1,a_2,\ldots,a_n$有奇$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(m^3/64)$,一次线段树操作涉及$\log_2n$次上推,因此每次操作时间复杂度高达$O((m^3/64)\log_2n)$,很慢。

如果有区间修改操作。我们可以计算差量数组后转成单点问题。对于给定向量$a_1,\ldots,a_n$,得到的差分量$b_i=a_i-a_{i-1}$,其中认为$a_0=0$。此时可以证明$a_l,b_{l+1},\ldots,b_{r}$张成的线性子空间与$a_l,a_{l+1},\ldots,a_r$张成的线性子空间相同。对于不同的区间操作可以采用不同的策略:

  • 区间赋值操作,实际上等价于$b_l,b_{r+1}$修改,$b_{l+1},\ldots,b_r$全部清$0$。
  • 区间加法操作,等价于$b_l,b_{r+1}$修改,其余元素不变。
  • 区间查询操作,查出$b_{l+1},\ldots,b_{r}$组成的线性子空间后把$a_l$插入即可。

提供一道题目

如果没有修改操作,只有区间查询,那么最简单的方式是使用猫树,构建的时间复杂度为$O(\frac{1}{64}m^2n\log_2n)$。查询的时间复杂度为$O(m^3/64)$。但是缺点是内存占用量是$O(\frac{1}{8}m^2n\log_2n)$。还有一种比较有效的方式,对于任意左边界$l$,我们将$a_l,a_{l+1},\ldots$逐一插入到集合中,真正会出现在线性基中的元素最多只有$m$个,记这些元素为$L(l)$。要为每个左边界计算一次难度比较高,但是可以发现$L(l)$与$L(l+1)$差别非常小,实际上$L(l)\subseteq L(l+1)+\left\{l\right\}$,因此我们可以$O(\frac{1}{64}m^3n)$预处理出$L$。之后每个区间查询,我们可以$O(m^3/64)$算出区间线性基。这种方式最大的优势内存是占用仅为$O(nm)$。