线性变换相关

FWT

快速沃尔什变换，与 FFT 有极大相似之处。

用于做一类形如 \(F_c\sum_{a \oplus b=c}A_a\times B_b\) 的问题，其中 \(\oplus\) 是一种线性变换，即 \(a \oplus b\) 是将 \(a,b\) 两个二进制数的第 \(i\) 分别做变换 \(\oplus_i\)（一般是异或，与，或中的一种）。

做法和 FFT 类似，计算 \(A * B\) 只需要先 \(FWT(A),FWT(B)\) 然后将对应位的点值乘起来得到 \(C\)，则 \(F=IFWT(C)\)。

证明懒得写。这玩意的本质是对于这种线性变换的每一位构造出一个变换矩阵，也就是按位独立。

所以可以只对部分位做，也可以对某一位做不同的运算。

板子

矩阵树定理+按位FWT

线性基/正交线性基

将若干个 \(k\) 位二进制数看成一堆 \(k\) 维向量，每维坐标取值只有 \(0,1\)。

定义向量加法 \(a+b\) 为不进位加法，即二进制下的异或。

则可以定义线性基 \(A\) 就是若干 \(k\) 维向量张成的线性空间 \(span(A)\)，也就是任选向量做加法所能得到的向量的集合。

定义向量内积 \(a·b\) 为 \(popcount(a\&b)\mod 2\)，则有结合律 \(w·(a+b)=w·a+w·b\)。

称两数 \(a,b\) 正交当且仅当 \(a·b=0\)。

这个结合律也可以用来证明 FWT 异或卷积。

线性基的秩：可以简单理解成构造出的线性基中插入的数的数量。

线性基的性质：对于线性基通过线性基中任意数异或得到的数 \(v\)，有 \(2^{m-k}\) 种选子集异或和的方法得到，其中 \(m\) 是向量个数。

集合幂级数

可以看作二进制意义下的生成函数。

正交线性基

设 \(A\) 的正交线性基 \(A'\) 满足：\(span(A')\) 是 \(span(A)\) 的正交补空间，也即 \(span(A')\) 中所有数和 \(span(A)\) 中所有数正交。正交线性基满足：对于 \(n\) 维向量构成的秩为 \(k\) 的线性基 \(A\)，其正交线性基 \(A'\) 的秩是 \(n-k\)。不难看出通过这一点，可以将复杂度优化成 \(2^{\frac{n}{2}}\)。

构造方法：首先正交线性基按每个数的最低二进制位存储，这些位恰好对应按高位存储的原线性基没有插入的几个位。对于一个最低位 \(i\)，其第 \(j\) 位为 1 当且仅当原线性基中最高位是 \(j\) 的，第 \(i\) 位也是 1。不难发现构造复杂度 \(O(n^2)\)。

线性基求交（其实很直观）：对于若干线性基求交，答案是这些线性基的正交线性基的并的正交线性基。

正交线性基性质：

对于线性基 \(A\)，设其秩是 \(k\)，设其集合幂级数=如下：若 \(u\subset span(A)\)，则 \([x^u]A=1\)，那么对 \(A\) 做 FWT 之后得到的 \(A_1\) 有什么性质？

结论是 \(A_1\) 的每个系数要么是 \(2^k\)，要么是 \(0\)，且满足 \([x^w]A_1=2^k\) 的 \(w\) 的所有取值就是 \(span(A')\)，其中 \(A'\) 是 \(A\) 的正交线性基。

CF1336E1/2