线性基小记

Blackbird137

什么是线性基

线性基大概可以理解为对于一组数 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;
}

例题

[链接登录后可见]

开关就是一个二进制数，改变一次状态就相当于异或，题目要求统计不同的数量，由于线性基中的每个元素不重复且可以表示出所有原数组的异或值，所以直接把所有开关压进线性基。由于线性基中每个数有选与不选两种情况，所以统计线性基中数的个数 sum，答案就是 2^{sum}。

[链接登录后可见]

注意到·异或存在 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 可以通过选中的元素表示出，则它一定和选中的元素中的某一个互换后仍然是满足要求的。所以我们只要尽可能地选价值更大的就一定是最优的。所以可以先按价值排序，从大到小选。判断异或和相等则直接套上一个线性基就行了。

[链接登录后可见]

有趣的思维题。按位考虑，如果序列 a 中一位出现的次数是奇数，那么怎么分其对答案都只贡献一次。把所有出现次数为奇数的位刨掉，剩下的位置出现次数就都是偶数，那么显然这样分出来的两个集合的值相等，所以最大化其中一个即可。

Ps：文章内容均为个人理解，如有错误欢迎指出。