@lijunhan

向量空间(Vector Space) （[1]第一章1.2节）

---

定义（注：这里没啥问题倒是。。只是全是复制粘贴不太好）

一个在域$F$上定义两种运算（加法、数乘）的集合$V$，为了保证对于所有$x,y\in V$以及$a\in F$，我们有$x+y$和$ax$是唯一的，这个集合需要满足如下条件：

（加法交换律）对于所有$x,y\in V$满足$x+y=y+x$

（加法结合律）对于所有$x,y,z\in V$满足$(x+y)+z=x+(y+z)$

（存在零元）存在一个元素$0$使得任意$x\in V$满足$x+0=x$

（存在加法逆元）对于所有$x\in V$存在一个$y\in V$使得$x+y=0$

（乘1不变）对于所有$x\in V$有$1x=x$

（数乘结合律）对于所有$a,b\in F$满足$(ab)x=a(bx)$

（分配律）对于所有$a\in F,x,y\in V$满足$a(x+y)=ax+ay$

（分配律）对于所有$a,b\in F,x\in V$满足$(a+b)x=ax+bx$

注意这个定义不只限于一般意义的向量$F^n$（即\left(\begin{array} aa_1\\a_2\\\dots\\a_n\end{array}\right)），更多例子可以看一下参考文献（注：复制粘贴后的定义下面的一坨东西太奇怪了，可以删去）

本文主要讨论的，是定义在$\mathbb{Z}/2\mathbb{Z}$（也就是模2意义下的整数，只有0或1）上的向量空间，此时加法运算即异或运算。下面给出该向量空间的定义。令$V=\{(a_1,a_2,\dots,a_n)|a_i\in \{0,1\}\}$，$\forall x=(a_1,a_2,\dots,a_n),y=(b_1,b_2\dots,b_n)\in V$，定义加法运算为$x+y=\{(a_1\oplus b_1,\dots,a_n\oplus b_n)\}$，数乘运算为$1x=x,0x=0$。验证一下上述定义发现成立。

（注：整数不是域，是integral domain，因为域必须有乘法逆元）

子空间（[1]第一章1.3节）

---

线性相关和线性无关([1]第一章1.5节)

---

对于定义在$F$上的向量空间$V$其中的一个子集$S=\{x_1,x_2,\dots,x_n\}$，如果它线性相关，那么存在非$0$的$a_i\in F$使得

$a_1x_1+a_2x_2+\dots+a_nx_n=0$

如果不存在这样的$a_i$，那么称$S$为线性无关。

如果在我们的异或空间里看的话，一个子集$S$是线性无关，当且仅当不存在非空子集$T\subseteq S$，使得$T$中的元素异或和为$0$。

基与张成空间([1]第一章1.4节，1.6节，1.7节)

---

对于一个$V$的子集$S=\{x_1,x_2,\dots,x_n\}$，它的张成空间$span(S)$定义为

$W=\{a_1x_1+a_2x_2+\dots+a_nx_n|a_i\in F\}$。即对于$S$中元素的线性组合组成的集合。

可以证明$W$也是一个向量空间，且$W$是$V$的子空间。

一个空间$V$的基，就是一个线性无关子集$S$使得$span(S)=V$。可以证明$S$是一个极大的线性无关子集（就是没法让它变得更大）

秩（第二章2.1节~第3章）

---

（注：拟阵别谈，除非你真的要用到拟阵；但下面似乎没有地方用到拟阵。拟阵的简单介绍在日报和集训队论文2018有吧，可以看一下了解一下，再来判断要不要提。不要随手搜一个书就摆上来。。

不过，你下面似乎也没用到秩？你可以把参考文献看一下再来回答这些问题）

基的性质

---

第2个即定义

第3个不是绝对。只是你为了方便，消元的过程消掉了而已。得把定义定清楚

第4个，，由第一个就能推得只要有$n$个元素就可以异或出$[0,2^n-1]$。$0$就是什么都不异或。

线性基的操作

---

说得很模糊，像是把我的意见直接添加上去一样。。

查询第k小

---

证明为什么这样是对的。你的例子太过于简单，还不足以搞明白这里到底是什么过程。。

可以考虑一下若$x<y$，且对应的二进制分解为$\{a_i\}$和$\{b_i\}$，那么为什么经过那个过程会有

$A_{a_1}\oplus A_{a_2}\oplus\dots\oplus A_{a_n}<A_{b_1}\oplus A_{b_2}\oplus\dots A_{b_m}$

显然，是因为你的操作使得对于每个$A_i$，它的最高位$j$满足$A_k(k\neq i)$的这一位为$0$。然后就可以证了。

查询第x的排名

---

方法2：意思就是经过了处理后，选择哪些基（这是个二进制数）就可以直接对应排名大小了。。

看起来没必要讲太多细节东西。。

求交

---

看起来也很简单，，假设有两个$V$的子空间$S,T$，他们的基分别是$\{a_i\},\{b_i\}$。

可以先得到子空间$W=span(\{a_i\},\{b_i\})$的基。我们选择一个特殊的基：$\{b_i\}\cup A$其中$A$是$\{a_i\}$的子集。于是$\forall a_i\notin A,$它们都有一个确定的表示方法：$a_i=\sum_j c_jb_j+\sum_{a_j\in T}d_ja_j$。这时可以发现$a_i-\sum_{a_j\in T}d_ja_j$是一个线性无关的东西

然后又由于$span(\{a_i-\sum_{a_j\in T}d_ja_j\})$和$span(A)$是不交的，所以所有$S\cap T$的也在这里面。所以这就是$S\cap T$的基。

求并

---

这里肯定不是指$S\cup T$，因为这个甚至不一定是向量空间。。（比如{0,1}和{0,10}，{0,1,10}不是向量空间。）

所以就是线性基合并吧，插一下就行了

你有兴趣补充上面的细节的话我会给更多的建议，如果想中途退出那尽快提出。。

参考文献（当然，我建议您把第一章看一遍。大部分都是OIer会的东西）

[1]Linear Algebra,Stephen H. Friedberg, Arnold J. Insel, Lawrence E. Spence,http://gen.lib.rus.ec/book/index.php?md5=DC97BEAD4DA44AE5F5DFAC814CF01401