文章目录

• 解析
• 实现
• 删除

所谓线性基，就是线性的基

（逃）

解析

何为线性基？
定义几何$B$为集合$S$的线性基,当且仅当:

.S任意子集异或和可以得到的结果，用B的子集都也可以得到，且B时所有这样的集合中元素最少的

线性基的一些重要的性质

1.线性基没有异或和为 0 的子集。
2.线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
3.线性基中每个元素的二进制最高位互不相同。

实现

累了
不想打字了
而且我也说不明白
大概就是利用异或的交换律的性质balabala
利用之前的和自己合体拼出S的所有元素
直接看代码吧

void solve(){mi[0]=1;for(int i=1;i<=50;i++){mi[i]=mi[i-1]*2;//printf("i=%d mi=%lld\n",i,mi[i]);}for(int o=1;o<=n;o++){ll x=a[o];//printf("o=%d x=%lld\n",o,x);int flag=0;for(int i=50;i>=0;i--){if((x&mi[i])==0) continue;else if(!p[i]){p[i]=x;break;}else{x^=p[i];}}} }

删除

有一个集合 $S$，要求支持加数和删除，动态维护线性基。

对于删除一个数 $x$，分类讨论：
如果 $x$ 不在线性基内：直接把这个数删掉即可。
如果这个数在线性基内：设每个元素在尝试插入线性基时异或的线性基的集合为 $P$，那么如果存在一个线性基外的元素 $y$ 的 $P$ 集合包含 $x$，说明这两个元素是等价的，直接把那个元素删去即可；否则，不仅要删除 $x$，还要去除其他元素异或 $x$ 的影响，设在线性基内且 $P$ 集合包含 $x$ 的最小元素为 $y$，则令 $x\oplus y$ 取代 $x$ 元素，并另其他在线性基内且 $P$ 集合包含 $x$ 的元素异或上 $y$。

可以离线时，线段树分治还是很香的。

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的模板：线性基的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。