专栏文章

【学习笔记】线性基

LLinkyChristian
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minoy6nd
此快照首次捕获于
2025/12/02 05:58
3 个月前
此快照最后确认于
2025/12/02 05:58
3 个月前
查看原文
模拟赛遇到一个笨比线性基题但是忘了怎么求编号......最后因读入T掉来不及修改赛后20s过题，惨痛教训。
线性基是一组极小的用于表达一个数集异或空间的基底。其满足以下性质：
1.能由原数集异或得到的任意一个数，线性基中都有且仅有一个子集能表示它。
2.由1得，线性基中不存在一个数能被其它元素异或得到。
3.由2得，线性基中不存在异或和为 00 的子集。
线性基不是唯一的，且不一定需要满足最高位互不相同，但我们构造时需要构造一个最高位互不相同的线性基，这样才能在加入元素时通过贪心判断新元素能否被原线性基表达。
假设我们已经有了一个最高位互不相同的线性基，现在加入一个新元素：
  • 如果不使用最高位与新元素最高位相同的基向量，那么其它所有向量无论如何组合也无法凑出最高位的 11，因此必定使用最高位与新元素最高位相同的基向量。
  • 对于新出现的最高位，重复以上操作。
显然不论我们以任何顺序插入元素，线性基大小都相同，得到以下性质：所有线性基大小相同，即对一个数集求线性无关的基底则其大小固定。
由此，我们构造线性基的代码已经可以写出来了：
CPP
for(int k=50; k>=0; k--) {    		
    if(num&(1ll<<k)) {    			
    if(!p[k]) {p[k]=num;break;}    			
    num^=p[k];    		
}
numnum 为新插入的数，pkp_k 为最高位为 kk 的基向量。
拓展：如何求原数集子集异或和的集合大小?
显然线性基的任意一个子集的异或和都不相同，所以其为 2线性基大小2^{线性基大小}
拓展：线性基构造出来的数，如何输出原数集中的对应方案？
我们对线性基中的每一个数用一个 bitset 记录其是由原数集中的哪些数异或得到的。具体而言：
CPP
bitset<N> pid[55];
for(int i=1; i<=n; i++) {
	cin>>a[i];
	bitset<N> id; id[i]=1;  
	for(int k=50; k>=0; k--) {    		
    	if(a[i]&(1ll<<k)) {    			
    	if(!p[k]) {p[k]=a[i],pid[k]=id;break;}    			
    	a[i]^=p[k],id^=pid[k];    		
	}
}
用线性基构造时，使用的基向量的 pidpid 异或和即为对应的原数集集合。
线性基的用处：

1.判断某个数是否可以被原数集的某个子集异或得到。

与往线性基中加数相同。

进阶： 判断某个数被原数集的某个子集异或得到的方案数。

任何数被线性基异或得到的方案数唯一，考虑没能加入线性基的数有 kk 个，显然这 kk 个数任选一个子集都能用线性基中的一个子集使其贡献为 00 ，因而每个数会有 2k2^k 中表达方法

2.判断原数集异或能得到的最大/最小值。

从高位到低位贪心，若该位为 00 且存在最高位为此位的基向量，则异或此基向量即可。
CPP
for(int i=50; i>=0; i--) if(!(ans&(1ll<<i))) ans^=p[i];

进阶：判断原数集异或能得到的第 kk 小值。

显然对于某个存在最高位为该位的位，我们都可以自由控制该位是否为 11 。
因此如果我们设置该位为 11 ，则增加了 2最高位低于该位的基向量个数2^{最高位低于该位的基向量个数} 个小于它的数。
CPP
ll ans=0,p=cnt;
for(Reg int i=62;i>=0;--i){
    if(!b[i]) continue;
    if(ans&(1ll<<i)){
        if(k>(1ll<<(p-1))) k-=(1ll<<(p-1)),ans^=b[i];
    }else{
        if(k>(1ll<<(p-1))) k-=(1ll<<(p-1));
        else ans^=b[i];
    }
    --p;
}
拓展：对于不去重的排名，考虑没能加入线性基的数有 kk 个，显然这 kk 个数任选一个子集都能用线性基中的一个子集使其贡献为 00 ，因而每个数会重复 2k2^k 次，若原答案为 ansans ，则不去重的答案为 2ans−1+12^{ans-1}+1 。
3.求一个数在原数集异或和中的排名。
与上类似，先判断该数能否被线性基表达出来，再依次枚举每位线性基中存在的位，加上 2最高位低于该位的基向量个数2^{最高位低于该位的基向量个数} 即可。
带删除线性基
首先需要知道每个时间点都干了些什么，如果是加了个数就需要预处理出这个数会在哪里被删掉。处理好这个之后，我们仍然按照时间处理操作，但是需要给插入线性基的数一个时间戳表示这个数被删除的时间，查询的时候只查询时间戳在当前时间之后的。对于线性基的每一位，时间戳应优先保留靠后的一个。
CPP
constexpr int MAXN=5e5+5;
int n,a[MAXN],del[MAXN];
unordered_map<int,int>mp;
struct{
	int p[32],t[32];
	void ins(int x,int tim){
		for(int i=30;~i;i--){
			if(!(x>>i)) continue;
			if(tim>t[i]) swap(x,p[i]),swap(tim,t[i]);
			if(!tim) return;
			x^=p[i];
		}
	}
	int ask(int tim){
		int res=0;
		for(int i=30;~i;i--) if(tim<t[i]) res=max(res,res^p[i]);
		return res;
	}
}LB;

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]>0) mp[a[i]]=i,del[i]=n+1;
		else del[mp[-a[i]]]=i;
	}
	for(int i=1;i<=n;i++){
		if(a[i]>0) LB.ins(a[i],del[i]);
		write(LB.ask(i));
	}
	return fw,0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...