Linear-basis

正交线性基。

参考 link。

orz Sooke。

线性基

回忆一下线性基，$\mathbb Z^{n}_2$ 上的一组线性无关的基。

$\mathbb Z^{n}_2$ 上的基本运算：

加法：不进位加法，就是异或。

点积：参考向量，$a\times b=\text{popcount}(a\&b)\bmod 2$ 。

回忆一下 FWT 的过程，会发现 $[x^u]F\to [x^v] \hat F$ 的转移矩阵系数为 $(-1)^{u\times v}$。

正交线性基

$a\times b=0$ 则称 $a,b$ 正交，记作 $a \perp b$，因为几何意义上是两向量垂直。

对于一 $\mathbb Z^{n}_2$ 的线性子空间 $A$，定义其正交补为 $\{x|\forall y\in A,x\perp y\}$。

首先如果 $a\perp x,b\perp x$，那么 $(a+b)\perp x$，这个可以分配律简单证。

因此正交补也可以找到一组基来表示，考虑一下基的大小，设原线性基大小为 $k$，以这 $k$ 个为基底，那么容易发现有 $n-k$ 维无关，因此正交补大小为 $2^{n-k}$。

考虑咋求，先把线性基消成最简，然后要和每个垂直，因此用原线性基空的行来放，然后如果和线性基中的有交就补上一个使得点积为 $0$ 。

//copy 
// Fennec's Algorithm
for (int i = n - 1; i >= 0; i--) {
    for (int j = i - 1; j >= 0; j--) {
        if (A[i] >> j & 1) { A[i] ^= A[j]; }
    }
}
for (int i = n - 1; i >= 0; i--) {
    if (A[i] == 0) {
        B[i] = 1 << i;
        for (int j = n - 1; j > i; j--) {
            if (A[j] >> i & 1) { B[i] |= 1 << j; }
        }
    }
}

时间复杂度 $\mathcal O(n^2)$ 。

记 $A$ 的正交线性基为 $A^{\perp}$。

线性基 FWT

挺秒的一个东西。

注意到线性基满足加法封闭，令 $*$ 为异或卷积，$\times$ 为点乘，$\hat A$ 为 $A$ FWT 后的结果，那么：

$$A*A=A\times 2^k\\ \hat A\times \hat A=\hat A\times 2^k$$

因此 $[x^u]\hat A=\{0,2^k\}$。

又由于 $[x^u]\hat A=\sum (-1)^{u\times v}[x^v]A$，那么 $\forall u\times v=0$，$\{u|[x^u]\hat A=2^k\}=A^{\perp}$，也就是正交补就是 $A$ FWT 后的结果。

线性基求交

已知线性子空间 $V_1,V_2$ 的基 $A_1,A_2$，求 $V_1\cap V_2$ 的基。

不用正交补的做法没有看懂qwq，感觉太引荐。

注意到令 $F_1=\sum [u\in V_1]x^u$，$F_2$ 同理，那么交可以用 $F_1\times F_2$ 来表示。

而 $V_1\cup V_2$ 可以用 $V_1*V_2$ 表示，而并是好求的，直接加入即可。

而上面线性基 FWT 正表示出了一种点乘和卷积之间的关系，令 $V_3$ 表示 $V_1\cap V_2$，注意下面的运算中，系数只区别是否是 $0$ 而不关系其具体值。

$$V_3=V_1 \times V_2\\ V_3^{\perp}=V_1^{\perp} * V_2^{\perp}\\ V_3=(V_1^{\perp} * V_2^{\perp})^{\perp}$$

可以这样做是因为正交补有可逆性。

因此求交复杂度也 $\mathcal O(n^2)$ 。

一般实现时如果需要卡常，如果是询问一个数是否能被 $A$ 表出，那么可以直接判断其是否与 $A^{\perp}$ 中每个元素正交即可，因为该关系可逆。

CF1336E2

已知 $n$ 个 $[0,2^m-1]$ 的数，对于每个 $0\le i\le m$，求所有能异或表出的数中，$\text{popcount}=i$ 的有几个。

$m\le 53$ 。

线性基大小如果 $\le m/2$，那么直接暴力。

否则考虑线性基可以通过其正交补 FWT 得到，而正交补大小是 $m-k$，可以暴力求出。

接下来只要做 FWT，然后把 $2^{m-k}$ 的系数除掉就可以。

由于 FWT 的系数只和 $u\& v$ 有关，因此只需要记录正交补中每个数的 $\text{popcount}$，就可以简单统计对每个 $i$ 的贡献了。

复杂度 $\mathcal O(n+2^{m/2})$ 。