线性基：线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。类似于基底的概念，只不过运算方式是异或。

性质：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void add(ll x)
{
    for(int i=60;i>=0;i--)
    {
        if(x&(1ll<<i))//注意，如果i大于31，前面的1的后面一定要加ll
        {
            if(d[i])x^=d[i];
            else
            {
                d[i]=x;
                break;//插入成功就退出
            }
        }
    }
}
void work()//处理线性基
{
	for(int i=1;i<=60;i++)
	for(int j=1;j<=i;j++)
	if(d[i]&(1ll<<(j-1)))d[i]^=d[j-1];
}
ll k_th(ll k)
{
	if(k==1&&tot<n)return 0;//特判一下，假如k=1，并且原来的序列可以异或出0，就要返回0，tot表示线性基中的元素个数，n表示序列长度
	if(tot<n)k--;//类似上面，去掉0的情况，因为线性基中只能异或出不为0的解
	work();
	ll ans=0;
	for(int i=0;i<=60;i++)
	if(d[i]!=0)
	{
		if(k%2==1)ans^=d[i];
		k/=2;
	}
}

d[i] 表示第 $i$ 为为1，前面位数都为0的基。线性基处理之后，会完成化简，成为最简的线性基。

对于求第 $k$ 小的值，将 $k$ 先转成二进制，假如 $k$ 的第 $i$ 位为1， $ans$ 就异或上线性基中第 $i$ 个元素。