lp3812 【模板】线性基

线性基这个名字似乎是来自于它的数学意义。它的用途一般是在集合异或的题目中简化复杂度。
对于关于一个数集的线性基,它是一个集合。这个集合包含的数大概是数集中的数取对2取对数个。
它满足以下性质:它们中的每个数异或在一起可以得到原数集中任何数的异或和。
它是一个尽可能小的集合。
它是「数集中线性无关的最大子集」。(这一定义会在之后的深入学习中概括)
它的每个数的二进制最高位互不相同。

构造一个线性基可以用贪心的构造法。
对于一个即将插入线性基中的数\(x\),我们必须尽量让它能够以某一种方式被线性基中已有的数构造出来。
我们不妨令线性基中第\(i\)个数表示的是最高位为第\(i\)位的数。
如果线性基中能够构造出这个数,那么显然,从高到低枚举每一个数,每一次都将它异或去最高位的线性基所代表的数,那么最终一定会有两种情况之一:
一:这个数存在,则这个数按照上述方法异或后最终肯定会变成0。
二:这个数不存在,则这个数按照上述方法异或后最终肯定会遇到某一位线性基,使得这个线性基并不存在。那么这个数就可以放到给定线性基上。
上述两个情况是很显然的,因为根本不存在上述两种情况之外的情况。对于任意一种情况它的较高位一定可以被异或掉,而随之诞生的较低位也可以依次按需异或掉。

为什么这样构造出来的东西一定是满足性质一的呢?如果原数集中任意一个数都可以通过线性基里的某些数异或得到,那么任意一些数的异或和也一定可以通过这些数在线性基里的表示法的异或和得到。

回到这一题。这些数中的最大异或和一定是线性基中的最大异或和。
根据最大异或和的贪心构造法(即从高到低尝试异或每一项,如果能变得更大就异或),这样得到的结果必然是一个原数集能够构造出的数。这是有线性基的插入方式决定的。
按照上述的插入方式,一个新的数\(x\)只会在它的某一位作为最高位在线性基中不存在的时候连同它剩余的位被插入。故而任何一个较后面的位的修改都一定是在原数集中可以构造出来的修改。
所以这一题可以用线性基解决。

#include<iostream>
#include<cstdio>

long long bs[105];
int n;
void init(){
	scanf("%d",&n);
	long long x;
	for(int i=1;i<=n;++i){
		scanf("%lld",&x);
		for(int j=50;j>=0;--j){
			if(x&(1ll<<j)){
				if(!bs[j]){
					bs[j]=x;
				}
				x^=bs[j];
			}
		}
	}
	x=0;
	for(int i=50;i>=0;--i){
		if(x<(x^bs[i])){
			x^=bs[i];
		}
	}
	printf("%lld\n",x);
}

int main(){
	init();
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。