Skip to main content

__debug's Home Keep it simple, stupid

线性基小结

这篇文章简单介绍了线性基, 证了证线性无关与拟阵的关系, 还有一些线性基的简单应用.

引入

先大概介绍一下线性基吧.

对于一个向量空间, 它的一个基就是一组线性无关的向量, 同时又能够张成整个向量空间. 同时可以证明对于一个向量空间, 每个基的大小都是一样的, 也就是这个空间的维度.

显然我们可以使用高斯消元来得到这些向量张成的线性空间的一组基. 然而这东西看起来在 OI 中没有什么用啊??

但是如果将向量之间的线性组合变为异或和的话, 那么就会有很多有趣的题目了.

比如说经典的最大异或和问题:

给定一组自然数, 求其中异或和最大的子集.

解法很简单, 高斯消元之后会形成一个上三角矩阵, 直接按位贪心即可.

注意到基的个数最多是 \(\log w\) 的, 并不需要真的高斯消元, 直接这样写即可:

void add(LL x)
{
    for (int i = SIZE - 1; i >= 0 && x; --i) {
	if (x >> i & 1) {
	    if (!a[i]) {
		a[i] = x;
		break;
	    }
	    x ^= a[i];
	}
    }
}

当然, 也可以消成对角矩阵, 这样虽然最后贪心算答案的时候会好写一点, 但维护线性基的时候会麻烦一些.

与拟阵的关系

设 \(A\) 是一个线性空间.

设 \(A\) 的所有线性无关子集为 \(\mathcal{I}\), 容易证明 \(M = (A, \mathcal{I})\) 是一个拟阵:

  • 遗传性: 线性无关组的子集一定线性无关
  • 交换性: 反证法. 设 \(|X| < |Y|\), 并且 \(\forall v \in Y - X\), \(X \cup \{v\} \not\subseteq \mathcal{I}\), 那么 \(Y\) 中的所有向量都可以被 \(X\) 中的向量线性表出. 但因为 \(Y\) 线性无关, 不可能被元素更少的集合完全表示, 矛盾.

然后就很多题可以愉快地贪心啦!

应用

一般而言, 我们可以在 \(O(\log w)\) 的时间内加入一组向量并维护线性基, \(O(\log^2 w)\) 的时间内合并两组线性基.

HDU3949 XOR

Description

给你 \(N\) 个 \([1, 10^{18}]\) 内的整数, \(Q\) 次询问, 每次询问选出一些(至少一个)数, 能凑出的异或和的第 \(K\) 小.

\(N, Q \le 10^4\)

Solution

线性基模板题, 我写的是消成上三角的方法. 注意能否凑出 \(0\) 的情况.

BZOJ4568 [SCOI2016] 幸运数字

Description

给你一颗 \(N\) 个点的树, 每个点有一个 \([1, 2^{60}]\) 的点权, \(Q\) 次询问, 每次询问选择 \(u\) 到 \(v\) 的路径上的这些点权使得异或和最大.

\(N \le 2 \times 10^4, Q \le 2 \times 10^5\)

Solution

先点分治, 处理完分治结构中每个点到分治祖先的基以后, 每次询问只需在分治结构中找到 \(LCA\), 合并一次基即可. 这样复杂度是 \(O(Q (\log N + \log^2 w))\) 的.

当然树链剖分和倍增也是可以的, 但是复杂度就变为 \(O(Q \log N \log^2 w)\), 因为每次询问要合并 \(\log N\) 次基.

BZOJ3105 [CQOI2013] 新 Nim 游戏

Description

一个游戏, 共 \(N\) 堆石子, 第 \(i\) 堆有 \(A_i\) 个. 在第一个回合中, 第一个游戏者可以直接拿走若干个整堆的火柴. 可以一堆都不拿, 但不可以全部拿走. 第二回合也一样, 第二个游戏者也有这样一次机会. 从第三个回合 (又轮到第一个游戏者) 开始, 规则和 Nim 游戏一样.

如果你先拿, 怎样才能保证获胜? 如果可以获胜的话, 还要让第一回合拿的火柴总数尽量小.

\(N \le 100, 1 \le A_i \le 10^9\)

Solution

首先这题就是要找出 \(A\) 这群向量中所有的线性无关子集中和最大的那个.

前面既然证明了是一个拟阵, 就可以直接贪心了. 先按 \(A_i\) 从大到小排序, 然后如果加入之后仍然线性无关就加入.

matthew99's 经典傻逼题

Description

给你一个 \(N\) 个点的带权无向图. 对于图中的任意一个点集 (可以为空或者全集), 所有恰好有一个端点在这个点集中的边组成的集合被称为割. 一个割的权值被定义为所有在这个割上的边的异或和.

一开始这张图是空图, 现在, 考虑给这张无向图不断的加边. 加入每条边之后, 你都要求出当前权值最大的割的权值, 注意加入的边永远都不会消失.

设 \(l = \log_2 w\), \(N \le 500, M \le 1000, 0 \le l < 1000\), 权值输入输出均为二进制

Solution

首先转化一下问题, 将边权异或到点上之后发现问题变为:

维护线性基, 需要支持插入, 修改 (这里是异或) 某个向量.

主要是如何快速应用修改操作. 考虑高斯消元的过程. 可以对于矩阵的每一行记录一个 \(from(i)\), 表示这一行是由哪些 向量 (注意这里不是指行) 异或过来的.

然后每次要修改某一个向量 \(x\) (将其变为 \(x \oplus y\)), 先找到最高位的 \(1\) 最低的一个行 \(p\) 满足 \(x \in from(p)\). 然后对于其他的满足 \(x \in from(i)\) 的行 \(i\), 用 \(p\) 去异或一下, 将向量 \(x\) 的贡献消掉. 最后将行 \(p\) 异或上 \(y\), 然后直接维护线性基即可.

查询自然也是按照套路来了. 时间复杂度 \(O(nm(n + l))\). 压位以后可以通过此题.

Comments

Comments powered by Disqus