题解 P3812 【【模板】线性基】
wrpwrp
2020-06-15 16:03:23
upd:补了点东西
## 用处
~~没用我学这东西干嘛~~
+ 快速查询一个数是否可以被一堆数异或出来
+ 快速查询一堆数可以异或出来的最大/最小值
+ 快速查询一堆数可以异或出来的第k大值
~~这么点？~~
还有点性质在下面 ~~可能有点用~~
## 性质
+ 原数列里的任何一个数都可以通过线性基里的数异或表示出来
+ 线性基里任意一个子集的异或和都不为$0$
+ 一个数列可能有多个线性基，但是线性基里数的数量一定唯一，而且是满足性质一的基础上最少的
## 原理&实现
由于我想写简单一点，直接对代码写，所以真正的关于线性代数的那一部分就没写了 ~~妄图掩盖自己不会的事实~~
### 约定
以下$p[i]$表示原序列的线性基数组。
### 构造
~~先贴代码~~
把一个数插入线性基：
``` cpp
inline void ins(LL x) {
for(R int i=62;i>=0;i--)
if(x&(1LL<<i)) {
if(!p[i]) { p[i]=x,cnt++; break; }
else x^=p[i];
}
}
```
人话描述：
+ 从高位到低位进行。
+ 如果$x_{(2)}$第$i$位为$1$，判断$p[i]$是否插入，没有就插入**并且退出**，否则就异或上$p[i]$去进行下一位操作 。
那么，通过观察这个构造，我们再来~~感性~~理解线性基。
+ 异或的一个小性质：$ x \oplus y \oplus y =x $。
+ 性质一：观察插入过程，如果没有成功插入，对于$x_{(2)}$的每一位，要不就是不存在，要不就是异或上$p[i]$变成了$0$，那么最终$x$如果没有插入，那就意味着原有的线性基可以把它异或出来，它就没有插入的必要了。而更显然的，线性基中的数肯定是可以表示的。于是**原序列中的每一个数都可以通过线性基表示出来。**
+ 性质二：假设出现了$p[1] \oplus p[2]\oplus p[3]=0$,那就会有$p[1]\oplus p[2]=p[3]$，根据之前的定义，$p[3]$是不会被插入的。所以也可以得出线性基的任意一个子集异或和都不为$0$，所以在之后求第$k$大的时候和一些别的时候，**注意特判$0$**。
+ 性质三：考虑分类讨论
+ 当所有元素都可以插入线性基的时候，性质三显然成立
+ 设有一个元素$x$不能插入线性基，那就会有$x=0$或者是$p[a]\oplus p[b]\oplus p[c]=x$。显然当$x=0$的时候无论如何都不能插入线性基，而另一种情况则代表等式$p[a]\oplus p[b]\oplus x=p[c]$也就是说如果先插入$x$，$p[c]$就无法插入了，又因为观察插入过程的时候，每一个插入的数对应着一位，所以$x$与$p[c]$相排斥只会影响一位上的问题，那也就代表着**线性基里的数可能不同，但是总数肯定是一定的**。
于是我们初步理解了线性基
### 查询一个元素是否可以被异或出来
从高到低，如果这一位为$1$就异或上这一位的线性基，把$1$消去，根据性质一，如果最后得到了$0$，那这个数就可以表示出来。
```cpp
inline int ask(LL x) {
for(R int i=62;i>=0;i--)
if(x&(1LL<<i)) x^=p[i];
return x==0;
}
```
### 查询异或最大值
按位贪心即可。
```cpp
inline LL askmx() {
LL ans=0;
for(R int i=62;i>=0;i--)
if((ans^p[i])>ans) ans^=p[i];
return ans;
}
```
### 查询异或最小值
其实异或的最小值一般来说就是线性基里的最小元素，因为插入这个元素的时候我们总是尽量让它的高位为$0$才来插入这一位。但是为什么是“一般”呢？因为有可能会有出现$0$，得要在插入的时候记下个标记来特判才行。
```cpp
inline LL askmn() {
if(zero) return 0;
for(R int i=0;i<=62;i++)
if(p[i]) return p[i];
}
```
### 查询异或第$k$小
这个东东我感觉实现还是有那么点点复杂的哈。
首先考虑，要是每一位的选择都不会影响下一位的话，那就可以直接从高到低按位去选择就行了，就类似于二叉树求$rank$的玩法。但是我们之前建出来的线性基是没有这个性质的。比如$p[3]=101_{2},p[0]=1_{2}$的时候就炸了。所以我们考虑重构一个数组$d$来解决这个问题。先上代码：
```cpp
inline void rebuild() {
cnt=0;top=0;
for(R int i=MB;i>=0;i--)
for(R int j=i-1;j>=0;j--)
if(p[i]&(1LL<<j)) p[i]^=p[j];
for(R int i=0;i<=MB;i++) if(p[i]) d[cnt++]=p[i];
}
```
那么这是在干啥呢，就是在尽力把每个$p[i]$只留下第$i$位的$1$，从而使得各个位之间互不影响，也就是说它的理想效果如下：
$p[0] ~0~0~0~0~1$
$p[1] ~0~0~0~1~0$
$p[2] ~0~0~1~0~0$
$p[3] ~0~1~0~0~0$
$p[4] ~1~0~0~0~0$
但有时候并不能达到这个样子，可能会出现如下情况：
$p[0] ~0~0~0~0~1$
$p[1] ~0~0~0~0~0$
$p[2] ~0~0~1~0~0$
$p[3] ~0~1~0~0~0$
$p[4] ~1~0~0~1~0$
但是这个时候我们注意到，我们的目的已经达到了，互不影响的任务已经达成了，显然此时为$0$的$p$值不会对排名有任何影响，不用管它了。把信息导入到$d$数组后，查询$k$小代码不难写出：
```cpp
inline LL kth(int k) {
if(k>=(1LL<<cnt)) return -1;
LL ans=0;
for(R int i=MB;i>=0;i--)
if(k&(1LL<<i)) ans^=d[i];
return ans;
}
```
其实我个人觉得这个代码还得要自己理解一下。
~~背板子也行~~
但是这样其实还不太对，因为我们并没有考虑$0$的情况，所以还要去考虑一下$0$的情况，特判即可。
```cpp
printf("%lld\n",tmp-zero?kth(tmp-zero):0LL);
```
### 查询排名
```cpp
inline int rank(LL x) {
int ans = 0;
for(R int i = cnt - 1; i >= 0; i --)
if(x >= d[i]) ans += (1 << i), x ^= d[i];
return ans + zero;
}
```
注：这个$d[i]$是重建后的线性基。
于是线性基的基本操作就结束啦！
## 习题
1. [Luogu P3812 线性基](https://www.luogu.com.cn/problem/P3812)
[code](https://www.cnblogs.com/HN-wrp/p/12812931.html)
2. [Luogu P3857 [TJOI2008]彩灯](https://www.luogu.com.cn/problem/P3857)
[code](https://i-beta.cnblogs.com/posts/edit;postId=12812964)
3. [Luogu P4301 [CQOI2013]新Nim游戏](https://www.luogu.com.cn/problem/P4301)
[code](https://www.cnblogs.com/HN-wrp/p/12812983.html)
4. [Luogu P4570 [BJWC2011]元素](https://www.luogu.com.cn/problem/P4570)
[code](https://www.cnblogs.com/HN-wrp/p/12813004.html)
5. [HDU 3949 XOR](http://acm.hdu.edu.cn/showproblem.php?pid=3949)
[code](https://www.cnblogs.com/HN-wrp/p/12813014.html)
6. [Luogu P4151 [WC2011]最大XOR和路径](https://www.luogu.com.cn/problem/P4151)
[code](https://www.cnblogs.com/HN-wrp/p/12818708.html)
7. [Luogu P3292 [SCOI2016]幸运数字](https://www.luogu.com.cn/problem/P3292)
[code](https://www.cnblogs.com/HN-wrp/p/12820816.html)
## EX
[dalao博客](https://blog.sengxian.com/algorithms/linear-basis)