线性基初探

## 前置知识 位运算基本知识、异或 以及a xor x xor x=a ## 正文 有一道模版题是[P3812 【模板】线性基](https://www.luogu.org/problemnew/show/P3812) 线性基是向量空间的一组基，通常可以解决有关异或的一些题目。 通俗一点的讲法就是由一个集合构造出来的另一个集合，它有以下几个性质： * 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。 * 线性基是满足性质 1 的最小的集合。 * 线性基没有异或和为 0 的子集。 * 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。 * 线性基中每个元素的二进制最高位互不相同。 也就是说，我们可以令 $p_i$ 为最高位的$1$在第$i$位的线性基元素 为了更加形象地理解线性基，我们用以下图形表示一个数  我们将其当成一个二进制数，图中为100110，即38 把新的一个数$x$加入当前集合的线性基的方法如下： * 将$x$转成二进制，从$x$的高位往低位扫，如果第i位是1： * $a_i$不存在，则令$a_i=x$，结束 * $a_i$存在，将$x$异或上$a_i$，继续。 那么我们模拟一下依次把3,14,7,15的情形 插入3，发现$p_1$不存在，直接将$p_1$改成3：  插入14，发现$p_3$不存在，直接将$p_3$改成14：  插入7,，发现$p_2$不存在，得到  插入15，$p_3$已经存在了，将15异或上$p_3=14$，得到2，发现$p_1$存在，将2异或上3得到1，$p_1$不存在，令其为1，结束。  Hint：如果所有的$a_i$都存在，那么这个数必定会被异或为0（每一位1都从高位到低位被异或掉了），所以不存在一直继续的情况。 代码如下： ```cpp //插入 inline void insert(long long x) { for (int i=62;i>=0;i--) {//从高到低扫每一位 if (!(x>>i)) // x的第i位是0 continue; if (!p[i]) { p[i]=x; break; } x ^= p[i]; } } ``` 线性基还支持以下几个操作 查询原集合内任意几个元素异或和的最大值： 将线性基从高位向低位扫，若异或当前扫到的$a_i$能使答案变大，就把异或。 ```cpp //查询最大 for(int i=62;i>=0;i--) if((ans^p[i])>ans) ans^=p[i]; ``` 为什么能行呢？因为从高往低位扫，若当前扫到第 $i$ 位，意味着可以保证答案的第 $i$ 位为 $1$，且后面没有机会改变第 $i$ 位。而如果第1到第i-1位都是1，也比第i位是1少。 查询原集合内任意几个元素 xor 的最小值，就是线性基集合所有元素中最小的那个。 ```cpp //查询最小 for(int i=1;i<=62;i++) if(p[i]){ ans=p[i]; break; } ``` 因为这几个数异或的最小值一定在线性基相互之间的异或值里，而如果最小的$p_i$异或上任意另外一个$p_i$，都会产生一个更高位的1，所以会变大。 查询某个数是否能被异或出来，类似于插入，如果最后插入的数 $x$ 被异或成0，则能被异或出来。 ```cpp //查询某个数能否被异或出来 inline bool insert(long long x){ for(long long i=63;i+1;i--){ if(x>>i){ if(p[i]) x^=p[i]; else { p[i]=x; return 1; } } } return 0; } ``` ## 例题 按照难度排序的例题。 ### [P3812 【模板】线性基](https://www.luogu.org/problemnew/show/P3812) 这题就是裸的模版了，直接给代码QAQ ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=55; int n; long long a[maxn],p[maxn],ans; inline void insert(long long x){ for(int i=55;i+1;i--){ if(!(x>>i))//x的第i位是0 continue; if(!p[i]){ p[i]=x; break; } x^=p[i]; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); insert(a[i]); } for(int i=55;i+1;i--) if((ans^p[i])>ans) ans^=p[i]; printf("%lld\n",ans); return 0; } ``` ### [P4570 [BJWC2011]元素](https://www.luogu.org/problemnew/show/P4570) 和xor有关的题目，我们都可以想到线性基 我们了解过判断一个数能不能被异或出来的方法。先按魔法值排序，从大到小判断元素能不能被当前集合异或出来，不能异或出来就将其贡献加入即可（虽然看上去很不靠谱但是是对的） [代码](https://www.luogu.org/paste/kt6295wb) ### [P4151 [WC2011\]最大XOR和路径](https://www.luogu.org/problemnew/show/P4151) 虽然是黑题，但是显然恶意评分= = 题意是求1到n最长路径，路径长度的定义为路径上的边权的异或和 因为去环上走一圈回来，只是将原路径异或上这个环的长度（就算通过一条路去那个环，回来的时候这条路也会被异或抵消掉） 所以只要随便钦定一条1到n的路径，预处理图上所有的环的长度插入线性基，然后直接求异或最大和即可。 有一个很容易想到的“反例”是找另外一条1到n更好的路径，然而，这条路径可以由原路径和这条路径组成的环和原路径异或得到，从而改变了路径，因此没有影响~ [代码](https://www.luogu.org/paste/4ewxildc) ### [P3292 [SCOI2016\]幸运数字](https://www.luogu.org/problemnew/show/P3292) 比上一题难了，需要加上倍增LCA。在处理LCA的时候顺便处理好**倍增线性基**，每次查询时将有需要的倍增线性基插入处理答案的线性基。 详情见[代码](https://www.luogu.org/paste/5tm80y8n)。 ## 习题 按照难度排序的习题。 [P3857 [TJOI2008\]彩灯](https://www.luogu.org/problemnew/show/P3857) [P3292 [SCOI2016\]幸运数字](https://www.luogu.org/problemnew/show/P3292) [CF724G Xor-matic Number of the Graph](https://www.luogu.org/problemnew/show/CF724G) 进阶题：[P3265 [JLOI2015\]装备购买](https://www.luogu.org/problemnew/show/P3265)（实数的线性基） 所以说 求异或最大值首先就可以考虑线性基辣~