五个数：a[5]={6,7,2,3,4}，a[i]=
原始的线性基：
对于a[i]，如果a[i]的j位为1
- p[j]=0，p[j]=a[i]
- p[j]!=0,表明已经填入数了，a[i]^=p[j]，继续遍历新的a[i]的下面的位，判断是否是1
所以这五个数对应的行阶梯矩阵为：
如果p[j]=0，那么这个a[i]就先入为主的填到p[j]的位置，且不会再更新这个p[j]
如果p[j]已经有数了，那么消去a[i] j位的1（a[i]^=p[j]）,再往后找可以填入的p[j]，每次无法填入的时候都要消去a[i] j位的1，最终如果a[i]=0, 说明a[i]和a[i]前面出现的数异或会得到0。BZOJ2460就是用这种思路求解的。
这些不为0的p[i]又可以组合成 给出的n个数能得到的所有异或值
To sum up:
p[j]表示的是在顺序遍历a[]时，最先出现的 j位为1的异或值（可能是由1个数得到的，也可能是多个数异或得到的，但未必就是j位为1的最大的异或值）
a[i]无法填入（最终a[i]=0），说明a[i]和它前面出现的数异或会得到0。
这些不为0的p[i]又可以组合成 给出的n个数能得到的所有的异或值BZOJ2115就利用了这个性质
模版：
void getXian()
{
for(int i=0;i<n;i++)
{
for(int j=max_base;j>=0;j--)
{
if(a[i]>>j&1)
{
if(p[j])
a[i]^=p[j];
else
{
p[j]=a[i];
break;
}
}
}
}
} 力求满足对角矩阵的线性基：
最开始学线性基的时候，大佬们讲的都是这种线性基：https://blog.sengxian.com/algorithms/linear-basis
它和原始的线性基的不同之处在于：在把a[i]填入p[j]时，要用p[j]下面的行消去p[j]的j位之后的1,用p[j]消去p[j]上面行中j位为1的p[k] (因为不为0的p[j]的j位一定是1)。这样处理完之后的行阶梯矩阵就和对角矩阵很接近了，具体讲解在这里
所以这五个数对应的行阶梯矩阵为：
To sum up:p[j]表示由n个数得到的j位为1的最小的异或值，利用这个性质就可以求n个数异或得到的第k小的数了
注意：如果得到的线性基的p[j]不为0的数目num和给出的数字数目n相同的话，那么这n个数无法通过异或得到0
模版：
void getXian()
{
for(int i=0;i<n;i++)
{
for(int j=max_base;j>=0;j--)
{
if(a[i]>>j&1)
{
if(p[j])
a[i]^=p[j];
else
{
p[j]=a[i];
for(int k=j-1;k>=0;k--)
if(p[j]>>k&1)
p[j]^=p[k];
for(int k=j+1;k<max_base;k++)
if(p[k]>>j&1)
p[k]^=p[j];
break;
}
}
}
}
}
京公网安备 11010502036488号