什么是线性基
线性基大概可以理解为对于一组数 \(A_1,A_2...A_n\) ,构造出一个大小为 \(\text{O}\left(\log_2\text{N}\right)\) 的一个数组 \(P\)(\(\text{N}\) 即为数组 \(A\) 中数的值域),使得数组 \(A\) 中的任意数都可以由数组 \(P\) 中的数异或得出。
在满足此条件时,线性基的大小应该尽可能的小。
线性基的性质
-
数组能通过数组 \(A\) 中的数异或得出的数同样能够通过数组 \(P\) 中的数异或得出。
- 线性基能表示出数组的所有数,所以一定可以表示出数组中数的异或值
-
线性基中的每一个数在二进制形式下的最高位都不同。
- 如果线性基中有两个数在二进制形式下的最高为相同,那么显然这两个数可以合并为一个数。
-
线性基没有异或和为 \(0\) 的子集。
- 如果线性基的某些数的异或和为 \(0\),那么这些数中的某一些数的异或和一定等于另一部分的异或和,也就是说这两部分有一部分是多余的,所以必须舍去。
线性基的构造
设 \(P_i\) 为线性基中在二进制下最高位为 \(i\) 的数的值
每插入一个数 \(x\),就执行一遍下面的操作:
-
从高到低枚举二进制下的位数 \(i\) ,如果线性基中最高位为 \(i\) 的数即 \(P_i\) 还没有数存入,就把 \(x\) 存入 \(P_i\) ,完成插入。
-
如果线性基中最高位为 \(i\) 的数已经存在,那么 \(x=x \ \oplus\ P_i\)
-
如果 \(x\) 为 \(0\) ,完成插入。
Code
void build()
{
x=read();
for(int i=50;i>=0;--i)
if(x>>i)
//如果 x 的前 i 位没有 1,那么下面的操作就没有意义
{
if(!p[i])
{
p[i]=x;
break;
}
x^=p[i];
}
}
为什么这么做可以构造出线性基?
如果找到了一个没有存入任何数的 \(P_i\),那么把 \(x\) 存入后就可以直接表示出 \(x\)。
如果找到了一个已经存入数的 \(P_i\),那么只要线性基能表示出 \(x\ \oplus \ P_i\) 那么 \(x\) 就可以通过 \(P_i\ \oplus\ \left(x\ \oplus\ P_i\right)=x\) 表示出。
而如果 \(x_{(2)}\) 的第 \(i\) 位为 \(1\),那么由于 \(P_i\) 的第 \(i\) 位一定为 \(1\) ,所以两数异或后 \(x\) 的第 \(i\) 位一定为 \(0\),这样一位一位地做,最终肯定会使 \(x\) 变为 \(0\)。
线性基的复杂度
我们需要一个大小 \(\text{O}\left(\log_2\text{N}\right)\) 的数组来存储所有的 \(P_i\),故空间复杂度 \(\text{O}\left(\log_2\text{N}\right)\)。
每插入一个数要遍历一边 \(P\) 数组,故时间复杂度也是 \(\text{O}\left(\log_2\text{N}\right)\)。
非常优秀
线性基的应用
求一组数中取任意数能得到的异或最大值
因为在原数组中异或得到的数也能在线性基中异或得到,所以问题就转换成了在这组数的线性基中找到异或最大值。
我们可以从高到低枚举位数 \(i\),记 \(ans\) 为当前能得到的异或最大值,则如果 \(P_i\ \oplus\ ans>ans\),那么就令 \(ans=P_i\ \oplus\ ans\)。
因为 \(P_i\) 的第 \(i\) 位为 \(1\),如果 \(ans\) 的第 \(i\) 位为 \(0\),那么异或后 \(ans\) 的第 \(i\) 为就变成了 \(1\),即使后面几位再小,\(ans\) 也会变大,所以异或更优。
而如果 \(ans\) 的第 \(i\) 位为 \(1\),那么异或后 \(ans\) 的第 \(i\) 为就变成了 \(0\),即使后面几位再大, \(ans\) 也会变小,所以不异或更优。
因为是从高位到低位计算的,所以后面位数的计算不会影响前面位数的计算,所以是最优的。
Code
int getmax()
{
int ans=0;
for(int i=50;i>=0;--i)
if((ans^p[i])>ans)
ans^=p[i];
return ans;
}
最小值同理。
判断一个数能否通过一组数中任意数异或得到
假如判断的数是 \(x\) 那么从高到低枚举 \(x\) 的每一位,如果第 \(i\) 位为 \(1\),那么就把它异或上 \(P_i\),如果枚举完后 \(x\) 为 \(0\),那么就可以表示出。
证明同理插入证明。
Code
bool check(int x)
{
for(int i=50;i>=0;--i)
if((x>>i)&1)
x^=p[i];
return x==0;
}
例题
Luogu P3812 【模板】线性基
<button class="accordion">Luogu P3812 【模板】线性基 解析
线性基求异或最大值的板子,不多说了
Luogu P3857 [TJOI2008]彩灯
<button class="accordion">Luogu P3857 [TJOI2008]彩灯 解析
开关就是一个二进制数,改变一次状态就相当于异或,题目要求统计不同的数量,由于线性基中的每个元素不重复且可以表示出所有原数组的异或值,所以直接把所有开关压进线性基。由于线性基中每个数有选与不选两种情况,所以统计线性基中数的个数 $sum$,答案就是 $2^{sum}$。
Luogu P4570 [BJWC2011]元素
<button class="accordion">Luogu P4570 [BJWC2011]元素 解析
注意到异或存在 $a \ \oplus\ b=c$ 时则 $b \ \oplus\ c=a$ 的性质,所以如果选择一个元素 $x$ 时出现了和已选中元素的非空子集 $a$ 异或为 $0$ 的情况,即:$a_{p1} \ \oplus\ ...\ \oplus\ a_{pk}=x$,则子集中任意一个数和 $x$ 互换后异或和也是 $0$,例如把 $x$ 和 $a_{p1}$ 互换后即为 $x \ \oplus\ ...\ \oplus\ a_{pk}=a_{p1}$。
换句话说,如果一个元素 \(x\) 可以通过选中的元素表示出,则它一定和选中的元素中的某一个互换后仍然是满足要求的。所以我们只要尽可能地选价值更大的就一定是最优的。所以可以先按价值排序,从大到小选。判断异或和相等则直接套上一个线性基就行了。
Atcoder ABC141F Xor Sum 3
<button class="accordion">Atcoder ABC141F Xor Sum 3 解析
有趣的思维题。按位考虑,如果序列 $a$ 中一位出现的次数是奇数,那么怎么分其对答案都只贡献一次。把所有出现次数为奇数的位刨掉,剩下的位置出现次数就都是偶数,那么显然这样分出来的两个集合的值相等,所以最大化其中一个即可。
待更新。。。
Ps:文章内容均为个人理解,如有错误欢迎指出。