线性基
线形基
给定一组$\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。
这里有一道题目。
问题11：给定$N$个数$A_1,\ldots,A_N$和$B_1,\ldots,B_N$以及$M$，要求选择一个下标集合$I$，满足$\oplus_{i\in I}A_i \leq M$的前提下，计算最大的$\oplus_{i\in I}B_i$。其中$0\leq A_i,B_i,K\leq 10^{18}$，$1\leq N\leq 10^6$。
一道题目。
记$H=\lceil \log \max_{i,j} A_i,B_j \rceil$
首先对于任意$i\neq j$，我们可以将$A_i$和$B_i$分别替换为$A_i\oplus A_j$和$B_i\oplus B_j$，这不会影响我们问题的答案。
因此我们可以找到一组$A$上的最大线性无关基底，下标集合记作$L_A$。将$N-I$下标的值，我们可以利用$L_A$中的元素将他们的$A$属性消除为$0$，而这时候它们的成本为$0$，因此它们的$B$值可以被任意选择，我们将它们的$B$属性建立一个线性基$X$。
通过类似的方式可以保证$L_A$中所有下标的$A$属性最高位都互不相同，我们可以从按最高位的大小从大到小暴力枚举$L_A$中的所有元素是否出现在结果中，利用剪枝和预处理我们可以保证最多只会有$2H$种可能的情况需要考虑。
因此总的时间复杂度为$O(NH+H^2)$。这里默认使用了位运算来避免操作单个位。
环、奇环、偶环
考虑$\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$插入即可。
提供一道题目。
题目1：给定$n$个元素$a_1,\ldots,a_n$，以及$m$个查询，第$i$个查询要求判断是否存在一个$a_{l_i},\ldots,a_{r_i}$的子集，其异或和正好等于$x_i$。其中$1\leq n,m\leq 10^6$，且$0\leq a_i\lt 2^{60}$。
提供一道题目。
我们可以在基础的线性基上加上一个过期时间的概念。假设当前的基为$B$，当插入一个新元素$e$时，如果这个元素不存在之前，那么新的基为$B+e$。否则必定存在$B$的某个子集$b$，使得子集中所有元素的异或和等于$e$。这时候类似于我们用LCT维护动态最小生成树的方式，我们选择一个在$e$之前过期的$b$中元素$t$进行替代（如果有多个，则选择最早过期的）。这时候最新的基为$B-t+e$。接下来我们考虑如何处理询问某个元素是否在基中。
接下来在时间点$y$的时候判断$x$是否处于$B$张开的空间中。我们只需要找出异或和为$x$的子集$b$中最早过期的元素，判断它是否在$y$或之前过期。
回到问题，当我们有这样一个数据结构的时候，我们只需要维护一个带过期时间的线性基。之后我们离线请求。之后我们将前面提到的将$a_i$的过期时间设置为$i+1$。我们按照$i$的顺序插入$a_i$。当插入$a_i$后我们回答所有右边界为$i$的请求，即判断线性基在时间$l$的时候是包含元素$x$。
时间复杂度为$O((n+m)\log_2 M)$。
线性基与线性子空间的双射关系
给定线性基$B$，可以唯一的确定其展开的子空间$S$。但是一般给定子空间，是不能唯一确定线性基的。因为同一个子空间中可能有多个线性基。
考虑给定子空间，确定其中的一组线性基。我们可以先找到其中一组最大线性无关组，之后进行高斯消元，将矩阵化成上三角形，且满足每个向量的最高位的$1$是唯一的，换言之如果向量$x$的最高位为第$k$位，则其余向量的第$k$位全为$0$。这是很容易做到的。
之后考虑这种形式的线性基的特点，我们将线性基中所有向量按照最高位出现的位置进行排序，分别记作$x^{(1)},x^{(2)},\ldots,x^{(t)}$。这时候可以发现张开的子空间（我们把$0$视作第$0$小的）中第$1$小的元素为$x^{(1)}$，第二小的为$x^{(2)}$，之后是$x^{(1)}+x^{(2)}$。可以发现这很类似于二进制进位的规则。因此第$k$小的向量为$\sum_{i=1}^t[k_i=1]x^{(i)}$，其中$k_i$表示$k$的二进制第$i$位。如果两个线性基张开的子空间相同，则基中最小的向量一定相同，第$2^i$小的向量也一定相同，因此所有向量都一一匹配。这时候可以发现线性基和子空间存在一个双射关系，其中线性基中第$i$小的元素为线性子空间中第$2^i$小的向量。
题目1：给定所有小于等于$k$的数，它们组成的线性空间中存在多少个不同的线性子空间。其中$1\leq k< 2^{60}$，结果对素数$p$取模。
提供一道问题。
我们可以通过上面提到的高斯消元法，利用线性基和线性子空间的一一对应关系，枚举线性基来枚举线性子空间。
做法类似于数位dp，记$dp(i,j,ceil)$表示前$i$个二进制，前$j$个线性基，$ceil=1$表示最大值正好等于$k$。这样时间复杂度和空间复杂度都是$O(2\times 60^2)$。
题目2：给定$n$个数$a_1,\ldots,a_n$，要求计算它们所有非空子集异或和中第$k$大的元素。
提供一道题目。
上面的高斯消元法得到的线性基$x_1,\ldots,x_t$，答案为$\sum_{i=1}^t[k_i=1]x^{(i)}$。
线性基下的最大最小运算
给定一个线性基$L$，把它消成上三角矩阵后，记$L_i$表示最高二进制为第$i$位的向量，它可能不存在。$L$张开的线性子空间为$V$。
接下来记:
- $M(x)=\max \left\{y\oplus x| y\in V \right\}$
- $m(x)=\min \left\{y\oplus x| y\in V \right\}$
下面我们证明它们满足如下运算规则：
- $M(x)\oplus M(y)=m(x\oplus y)$
- $m(x)\oplus m(y)=m(x\oplus y)$
- $M(x)\oplus m(y)=M(x\oplus y)$
先证明第一条：
考虑$M(x)=x\oplus X$，$M(y)=y\oplus Y$，$m(x\oplus y)=x\oplus X\oplus y\oplus Y'$。其中$X,Y,Y'\in V$。
通过反证法，假设二者不同，记$k$是$M(x)\oplus M(y)$与$m(x\oplus y)$不同的位中最高的一位，此时一定有前者为$1$，后者为$0$（根据$m$运算的定义），且$Y$与$Y'$第$k$位不同。那么$Y$和$Y'$除了后$k$位可能不同以外，其它位应该完全相同。由于$Y$和$Y'$的第$k$位不同，因此可以断定$x\oplus X$的第$k$位一定为$1$（否则这时候$L_k$不存在，那么$Y$和$Y'$的第$k$位由更高位所决定，而它们更高位完全一致，因此它们的第$k$位应该也完全相同）。这时候$Y\oplus y$的第$k$位是$0$，而$Y\oplus y'$的第$k$位为$1$，这时候有$M(Y)=Y\oplus y<Y\oplus y'$，这与$M$的定义相悖。因此假设不成立。
之后考虑第二条（证明类似）：
考虑$m(x)=x\oplus X$，$m(y)=y\oplus Y$，$m(x\oplus y)=x\oplus X\oplus y\oplus Y'$。其中$X,Y,Y'\in V$。
通过反证法，假设二者不同，记$k$是$m(x)\oplus m(y)$与$m(x\oplus y)$不同的位中最高的一位，此时一定有前者为$1$，后者为$0$（根据$m$运算的定义），且$Y$与$Y'$第$k$位不同。那么$Y$和$Y'$除了后$k$位可能不同以外，其它位应该完全相同。由于$Y$和$Y'$的第$k$位不同，因此可以断定$x\oplus X$的第$k$位一定为$0$（否则这时候$L_k$不存在，那么$Y$和$Y'$的第$k$位由更高位所决定，而它们更高位完全一致，因此它们的第$k$位应该也完全相同）。这时候$Y\oplus y$的第$k$位是$1$，而$Y\oplus y'$的第$k$位为$0$，这时候有$m(Y)=Y\oplus y>Y\oplus y'$，这与$m$的定义相悖。因此假设不成立。
之后考虑证明第三条（证明类似）：
考虑$M(x)=x\oplus X$，$m(y)=y\oplus Y$，$M(x\oplus y)=x\oplus X\oplus y\oplus Y'$。其中$X,Y,Y'\in V$。
通过反证法，假设二者不同，记$k$是$M(x)\oplus m(y)$与$M(x\oplus y)$不同的位中最高的一位，此时一定有前者为$0$，后者为$1$（根据$M$运算的定义），且$Y$与$Y'$第$k$位不同。那么$Y$和$Y'$除了后$k$位可能不同以外，其它位应该完全相同。由于$Y$和$Y'$的第$k$位不同，因此可以断定$x\oplus X$的第$k$位一定为$1$（否则这时候$L_k$不存在，那么$Y$和$Y'$的第$k$位由更高位所决定，而它们更高位完全一致，因此它们的第$k$位应该也完全相同）。这时候$Y\oplus y$的第$k$位是$1$，而$Y\oplus y'$的第$k$位为$0$，这时候有$m(Y)=Y\oplus y>Y\oplus y'$，这与$m$的定义相悖。因此假设不成立。
提供几道用到这个结论的题目：