正交线性基

看了一晚上Sooke’s 正交线性基的介绍，现在已经变成线性代数人了。

格物致知。

$\mathbb Z_2^n$ 表示 $n$ 维，每维 $\bmod \ 2$ 的空间，我们称这其中选出的一组线性无关的向量为线性基，一般按照最高位来存储线性基。

我们在这个空间中发掘向量的意义，我们发现向量的加法 $X+Y$ 等价于数的异或，向量的内积 $X\cdot Y=\sum_ix_iy_i\bmod2$ 等价于 $\text{popcount}(x\cap y)\bmod 2$ 。

仅仅是套了一个模意义，所以加法和乘法的各种性质都还是有的，例如分配律 $A\cdot(B+C)\equiv A\cdot B+A\cdot C\pmod 2$ 。

定义两个向量正交当且仅当其内积为 $0$ ，即 $\text{popcount}(x\cap y)\equiv 2\pmod 2$ 。

理解成抽象版本的“垂直”就好。

称 $\text{span}_A$ 为线性基 $A$ 张成的空间，称各位的 $1$ 被某个向量独占的线性基为高斯消元后的线性基。

下面给出「正交线性基」的概念，一个线性基 $A$ 的「正交线性基」 $\widehat A$ 满足以下性质：

$\text{span}_{\widehat A}$ 为 $\text{span}_A$ 的正交补空间（定义）。
$\widehat A$ 的每个向量与 $A$ 的每个向量均正交。
$\text{span}_{A\cup \widehat A}=\mathbb Z_2^n$ 。

同时满足 $2$ 性质和 $3$ 性质其实也可以成为一个充要条件。

关于正交补空间的定义，就是与该空间正交的所有向量的集合。

来个通俗一点的例子的话，由 $(1,0,0)$ 和 $(0,1,0)$ 张成的空间是 $\{(x,y,0)|x,y\in\mathbb R\}$ ，其正交补空间为 $\{(0,0,z)|z\in\mathbb R\}$ ，其正交补空间的一个基是 $\{(0,0,1)\}$ 。

等价性：易证若 $B$ 是 $\widehat A$ ，则 $(\forall C,\text{span}_C=\text{span}_B),C$ 也是 $\widehat A$ ，即一个线性基的等价线性基（张成的空间相同）在此处也具有一样的等价性。

考虑由 $B$ 转化为 $C$ 的过程，就是每次从 $B$ 中拿出两个向量 $a,b$ ，将 $a+b,b$ 放回去。

由性质 $\forall c\in C,a\cdot c=b\cdot c=0$ ，则 $(a+b)\cdot c=a\cdot c+b\cdot c=0$ ，符合定义。

所以在线性基中，我们称 $A=B$ 当且仅当 $\text{span}_A=\text{span}_B$ ，此时两个线性基已经完全等价。

好好好不当形式化小鬼了，我们来说说构造方法和应用：

构造方法

首先对 $A$ 进行高斯消元。
为了满足性质 $3$ ，我们需要 $\widehat A$ 的秩 $r_{\widehat A}=n-r_A$ ，所以 $\widehat A$ 在 $A$ 的非关键位（没有哪个向量的最高位是该位） $i$ 上一定要是 $1$ ，即 $\widehat A_{i,i}=1$ 。
接着若 $A_{j,i}=1$ 且 $\widehat{A}_{i,i}=1$ ，则 $\widehat{A}_{i,j}=1$ ，这是为了满足两个基必须正交，这样构造出来的 $A_j\cdot \widehat A_i=2\equiv 0\pmod 2$ ，由于已经高斯消元过原始集，所以将 $\widehat A_{i,j}$ 置为 $1$ 并不会影响与 $A$ 中其他向量的乘法结果。

写作代码的话大概是这样：

UF(i,63,0) UF(j,i-1,0) if(p[i]>>j&1) p[i]^=p[j];
UF(i,63,0) if(!p[i]) {
    s[i]=1<<i;UF(j,63,i) if(p[j]>>i&1) s[i]|=1<<j;
}

（p[] 是原始基，s[] 是正交基，此处 s[] 按照最低位存储。）

复杂度 $\Theta(\omega^2)$ ，我并没有找到良好的 $\Theta(\omega)$ 实现方法，可以规约到矩阵的转置上。

应用

终于到这一 part 了。

要是我来看这篇 blog 我非被前面吓跑不可。

线性基求交

其实就是当年老是学不会线性基求交才了解到的正交线性基。

定理： $A\cap B=\widehat{(\widehat A\cup \widehat B)}$ 。

（这个 \widehat 好抽象哈哈哈哈哈哈哈哈哈。）

所以我们就可以把线性基写成一个方便的 $\Theta(\omega^2)$ 快速求异或意义下交并的数据结构：

struct L {
    ll p[64];
    L() {memset(p,0,sizeof p);}
    ll &operator[](int x) {return p[x];}
    void operator+=(ll x) {
        UF(i,63,0) {
            if(!(x>>i&1)) continue;
            if(p[i]) x^=p[i];
            else return void(p[i]=x);
        }
    }
    L(ll s[],int n) {L();F(i,0,n) *this+=s[i];}
    L operator~() {L s;
        UF(i,63,0) UF(j,i-1,0) if(p[i]>>j&1) p[i]^=p[j];
        UF(i,63,0) if(!p[i]) {
            s[i]=1<<i;UF(j,63,i) if(p[j]>>i&1) s[i]|=1<<j;
        } return L(s.p,63);
    }
    L operator|(L b) {F(i,0,63) b+=p[i];return b;}
    L operator&(L b) {return ~(~*this|~b);}
}