线性基三个性质：

1. 原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
2. 线性基里面的任意一些数异或起来都不能得到0
3. 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

构造：arr数组为线性基数组，x为要插入的元素。

void add(ll arr[],ll x) {    for (int i = 63; i >= 0; i--) {        if (x & (1ll<

　　arr数组中存的元素arr[i]为二进制最高位1在第i+1位，如果这个位置已经有值了的话就对异或之后的值进行判断。

 

可用于求一组数异或后的最大值：

ll work(){    ll ans=0;    for(int i=63;i>=0;i--)    if((ans^d[i])>ans) ans^=arr[i];    return ans; }

 

也可用于求一组数异或后的最小值：

ll work() {    for (int i = 0; i <= n; i++) {        if (arr[i]) return arr[i];    }}

 

 

 

求第k小：

void work()//处理线性基{    for(int i=1;i<=60;i++)    for(int j=1;j<=i;j++)    if(d[i]&(1<<(j-1)))d[i]^=d[j-1];}ll k_th(ll k){    if(k==1&&tot

 

题目明天再写~

更多好题（难度非递增）：

   | 

  |

 

 

　　参考：