解释一下
高斯消元后有零行要k–的原因
有零行意味着要对0进行异或
这会使得下列算法无法求得真正第k小的ans
//如k=4(100) 与k=5(101)
这二者差的就是开头的零行(二进制表示差最后一个1)
很明显多一个零行不会让其从
k=4变到k=5 因为与0异或不改变结果
int i=1;
while(k)
{
if(k&1)ans^=a[i];
k=k>>1ll;
i++;
}
因此我们在求得消元后的a[i]后
对a[i]从小到大排序 且不能带零行排序
我们对零行只使用一次 就是求k=1时候使用
然后k>1时候无需考虑零行 用上面我们排好序的a[i]
套用这个算法求ans即可
int i=1;
while(k)
{
if(k&1)ans^=a[i];
k=k>>1ll;
i++;
}