线性基 #

朴素线性基 #

这里放纯模板题 LG P3812 【模板】线性基 loj 114. k 大异或和 NC xor序列

hdu2025多校2 子集 #

给定一个 $n$ 元数组 $a_i$，要求从选出下标不相邻的一些元素使得异或和最大，求最大值 $1 \leq n \leq 50, 1 \leq a_i \leq 10^18$，另设空间 3M 的空间限制

• 这个空间限制限制了开大数组，折半搜索等难以实现
• 我们使用线性基，注意到我们选取的数越多越优，所以我们不会隔 $3$ 个以上选数，事实上这就是一个很强的剪枝，可以直接 $dfs$ 剪枝通过

LG P4570 [BJWC2011] 元素 #

给定 $n$ 个数字 $a_i$ 和权值 $w_i$，现要选择一个集合使得集合中任意子集的数字异或和不为 $0$，并最大化权值之和 $1 \leq n \leq 1000, 1 \leq a_i \leq 10^{18}, 1 \leq 10^4$

• 利用异或性质可以证明，对于一个集合我们总是可以贪心的选择最大权值的数字，所以我们排序后从大权值的数字开始选取即可，时间复杂度 $O(nlogW)$，$W$ 是数字最大值

LG P3857 [TJOI2008] 彩灯 #

朴素电灯问题。给定 $n$ 个灯泡和 $m$ 个开关，每一个开关连接若干的灯泡，每点击一次开关会改变与之连接的所有灯泡状态，初始时所有灯泡关闭，求最终所有灯不同开关状况的数量 $1 \leq n, m \leq 50$

• 注意到 $2^{50}$ 是存得下的，使用线性基直接求向量组的秩取 $2$ 的幂减一即可，使用高斯消元会繁琐且复杂度更劣一些，时间复杂度 $O(nm)$

NC 牛客周赛96F Zeeman的异或数组 #

给定一个 $n$ 元多重集合，每次操作可以选择至少一个数组将其异或和加入集合中，可以进行无穷次操作，问集合中的 mex 最大是多少 $1 \leq n \leq 5 \times 10^5, 1 \leq a_i < 2^{60}$

• 关注线性基的性质，若前 $k - 1$ 位上存在基向量则这些位上组合的数字都可以构造，mex会取到从低位第一个不存在基向量位上的最小值，即 $2^{k - 1}$
• 注意由于是可重集，$0$ 是一定可构造的，这里不需要特判

LG P3265 [JLOI2015] 装备购买 #

给定 $n$ 个 $m$ 维向量，每个向量对应一个权值，现要求一个最大的线性无关向量组使得所有向量可以被线性表出，同时最小化权值之和 $1 \leq n, m \leq 500, 1 \leq a_i \leq 1000$

• 线性代数中求极大线性无关组的板子题目，最小化权值排序后进行高斯消元即可达到目标
• 注意开long double，或者eps放得大一点double过了不懂为什么

LG P4839 P 哥的桶 #

给定 $n$ 个空集，和 $q$ 次询问或修改，有以下两种形式

1. 给定 $k, x$，在第 $k$ 个集合中插入元素 $x$
2. 给定 $l, r$，查询第 $l$ 个集合到第 $r$ 个集合所有元素的最大异或和

$1 \leq n, q \leq 5 \times 10^4, 0 \leq x \leq 2^{31} - 1$

• 线性基 + 线段树的一个题，由于线性基元素不超过 $O(log)$ 个，每次合并做一个暴力的线性基合并，线段树的每一个节点都维护一个线性基即可，查询也暴力的将若干线性基合并，时间复杂度 $O(nlognlog^2x)$(线性基的暴力合并是两个log的)

LG P4151 [WC2011] 最大XOR和路径 #

给定一张 $n$ 节点 $m$ 条边的无向带边权连通图，定义路径权值为路径上所有边的边权异或值(多次经过同一条边异或多次)，求从节点 $1$ 到节点 $n$ 的最大权值 $1 \leq n \leq 5 \times 10^4, 1 \leq q \leq 10^5$

• 一个奇怪的题，能理解但是感觉没理解本质，包括这里到达找了什么样的环（注意到环可以很多但是我们只选了部分），且为什么在异或的线性空间下，这一部分环是构造出所有环的
• 首先使用dfs寻找到所有的环，并将环的异或值插入线性基，这是因为所有环都可以选择走或不走，获取任意一条从 $1$ 到 $n$ 的路径的权值，并考察这个权值异或上线性空间中的元素产生的最大值

NC [2025寒假营第六场I] BenzenE #

给定两个 $n$ 元数组 $a_i, b_i$，设另一个 $n$ 元数组 $c_i$ 满足 $c_i = a_i$ 或者 $c_i = b_i$，构造一个这样的数组 $c_i$ 使得 $\oplus_{i = 1}^n c_i = 0$，或者返回不可构造 $1 \leq n \leq 10^5, 0 \leq a_i, b_i \leq 2^{30}$

• 首先需要做这样的转化，将题意化归到使用若干数字异或出给定值的模型，假设我们全部选择 $a_i$，即目前选择的值是 $\oplus_{i = 1}^n a_i$，则问题就转化为选择若干 $a_i \oplus b_i$ 异或结果为 $\oplus_{i = 1}^n a_i$，这就是线性基可以解决的问题
• 另一个问题是这里需要还原方案，需要做特殊处理。注意有一个特判的点是全选 $a_i$ 就已经为 $0$ 了

前缀线性基 #

CF532 div2 F. Ivan and Burgers #

给定一个 $n$ 元数组 $a_i$，给定 $q$ 次询问，每次询问给定 $l, r$，查询区间 $[l, r]$ 中选择一些元素能产生的最大异或值 $1 \leq n, q \leq 5 \times 10^5, 0 \leq a_i \leq 10^6$

(下面分析复杂度视 $n$ 和 $max(a_i)$ 同阶)

• 首先可以使用线段树暴力维护若干线性基，时间复杂度 $O(nlog^2n + qlog^3n)$，或者由于线性基的可重复性可以使用ST表，时间复杂度 $O(nlog^3n + qlog^2n)$，但对这个题来说三只log是过不了的
• 一种存在于题解的做法是离线对 $r$ 排序后，考虑前 $r$ 个前缀对应的线性基只有 $O(logn)$ 种，所以最多维护 $O(logn)$ 个线性基，并进行修改，做到约 $O(nlog^2n)$，但事实上我没完全理解
• 可以使用前缀线性基，维护每一维向量的时间戳，这样我们有两种方法，维护一个线性基可以离线对 $r$ 排序，维护 $n$ 个线性基可以做到在线，每一次查询考虑对于当前 $r$ 对应的线性基中时间戳大于 $l$ 的，时间复杂度 $O((n + q)logn)$

LG P3292 [SCOI2016] 幸运数字 #

给定一棵 $n$ 节点的树，每个节点有对应权值 $a_i$，给定 $q$ 次询问，每次询问给定 $x, y$，查询从 $x$ 到 $y$ 的路径上的节点中选择一些权值产生的最大异或值 $1 \leq n \leq 2 \times 10^4, 1 \leq q \leq 2 \times 10^5, 1 \leq a_i \leq 2^{60}$

• 首先对于路径问题，转化为有根树会简单很多
• 把深度作为时间戳对每个节点到根的路径上做前缀线性基，这样每次查询我们把LCA的深度作为限制，用线性基合并获得路径上的数字查询最大异或即可，时间复杂度 $O(nlogW + q(logn + log^2W))$，$W$ 是数字最大值
• 朴素线性基也可以解决这个问题，这需要搭配树上倍增进行多次的线性基合并，时间复杂度 $O((n + q)lognlog^2W)$，复杂度是严格更劣的

NC 牛客周赛121 永远亭的小游戏（续） #

给定一个 $n$ 元数组 $a_i$，有 $q$ 次询问，每次询问给定一个区间 $[l, r]$，查询区间中是否存在子序列的乘积是完全平方数 $1 \leq n \leq 2 \times 10^5, 1 \leq q \leq 10^5, 1 \leq a_i \leq 100$

• 将质数作为位运算的bit即可转化为前缀线性基的板子