线性基(个人学习笔记)

前言：
个人学习用途，逻辑混乱。

线性基：由序列A构成的线性基，线性空间为任意取序列A中的数异或和。线性基的第i位数的最高位为第i位或不存在。

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

线性基构造

void base_insert(int x)
{for (int i = 63; i >= 0; i--){if (x & (1ll << i)){if (linebase[i]){x ^= linebase[i];}else{linebase[i] = x;break;}}}
}

线性基求异或和最大值

int maxn = 0;for (int i = 63; i >= 0; i--){maxn = max(maxn, maxn ^ linebase[i]);}

线性基求异或和最小值：linebase[0]即为最小值

线性基求异或和第k小：实际上由于开头提到的性质，可以将线性基与二进制下类比，高位 > 任取低位，所以将k分解二进制，k的第i位为1，则取线性基的第i个存在的数

int ans=0;
for(int i=0;i<=60;i++)if(linebase[i]!=0){if(k&1)ans^=d[i];k>>=1;}

收获：