基本知识
建议大家先了解一下基底
线性基就是基于基底推导出的一种知识，具有和基底类似的性质。
- 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值(原集合中的数字均能由线性基中的数字相互异或得出)
- 线性基是满足性质 1 的最小的集合。
- 线性基没有异或和为 0 的子集。(异或为 0 代表能构造出两个相同的数)
- 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
- 线性基中每个元素的二进制最高位互不相同
构造方法
1.不能插入线性基，即违反性质 3
违法性质3，即：新数字 x 预备插入 i 位置，出现d[1]^d[2]^d[3]···^d[i-1]^x=0，只要存在子集的异或和为 0，那么其全集的异或和也为 0，则不能插入线性基！
2.能插入线性基
利用性质 5 进行插入，性质 5 是性质 2 的推论，最高位不同，则不可能出现子集为 0 的情况
3.代码实现
inline void add(ll x)//把一个数插入线性基
{
for(int i=63; i>=0; i--)
{
if(x&(1ll<<i))
{
if(!p[i])//第i位上还没有
{
p[i]=x;
break;
}
else x^=p[i];// x 不能插入，x 在循环过程中会变为 0
}
}
}常见操作
1.询问某个数能否被线性基异或得出
inline bool ask(ll x)//询问某个数能否被线性基异或得出
{
for(int i=62; i>=0; i--)
{
if(x&(1ll<<i))
{
x^=p[i];
}
}
return x==0;\\利用性质2
}
\\其实就是模拟一边构造过程，当然也可以在构造过程中就打好标记2.询问在序列中取若干个数，所能取得异或和的最大值
inline ll ask_max()
{
ll ans=0;
for(int i=62; i>=0; i--)
{
if((ans^p[i])>ans) ans^=p[i];
}
return ans;
}3.询问线性基异或出的最小值
inline ll ask_min_1()
{
for(int i=0; i<=62; i++)
{
if(p[i]) return p[i];
}
}4.询问原序列能异或出的最小值（注意和操作 3 区分开）
如果原序列中有数字没进入线性基中，则代表原序列全集异或和为 0
inline ll ask_min_2()
{
if(cnt<n)//cnt表示线性基中的元素个数，n表示序列长度
return 0;
return ask_min_1();
}5.从线性基中取任意个元素，所得出的异或和中第 k 小的那个。
预处理
首先，要对线性基处理一下，使其变成如下式一样
处理方式：对于每一个 d[i]，枚举 j = i -> 1，如果 d [i] 的第 j位为1，那么 d[i] 异或 d[j−1] 。
求解
将 k 先转成二进制，假如 k 的第 i 位为 1 ， ans 就异或上线性基中第 i 个元素（注意不是直接异或 d[i −1]）。（原因自己以上面的例子，把第 1 小，到第 8 小全部列出即可明白）
void work()//处理线性基
{
for(int i=1; i<=60; i++)
{
for(int j=1; j<=i; j++)
if(p[i]&(1ll<<(j-1)))p[i]^=p[j-1];
if(p[i]) P[cnt++]=p[i];
}
}
ll k_th(ll k)
{
if(k==1) 0;//特判一下，假如k=1，则则不取的情况最优
work();
if(cnt<n)k--;//去掉0的情况，因为线性基中只能异或出不为0的解
long long ans=0;
for(long long i=0; i<cnt; i++)
{
if((k>>i)&1)
ans^=P[i];
}
return ans;
}6.从序列中取任意个数，所得出的异或和中第 k 小的那个。
跟 5 的区别在于，是从序列中提取，即在序列没有全部进入线性基的情况下，会出现异或和重复出现的情况，如 {1,2,3} 其子集，{1,2} 和 {3}，两者的异或和是相同的。
下面部分来自引用
序列的线性基为 $\mathfrak{B}$，B 为序列任意子集的异或和.
结论: 每个数都出现一样的次数, 且这个次数为$2^{n - \vert\mathfrak{B}\vert}$.
证明：所有不在线性基中的数的个数为$n-\vert\mathfrak{B}\vert$, 我们任意选择它的一个子集 S.
$\because\forall v \in S$, 有唯一的方式表达为$\mathfrak {B}$中向量的线性组合, 即$\mathfrak {B}$有唯一子集使得该子集中的向量异或和与 v 异或得 0.
$\therefore\forall x\in B$, 我们都能找到$2^{n - \vert \mathfrak{B}\vert}$种不同的选择方案, 使得异或值为 x.
又$\because$对于每个子集 S , 选择线性基中的向量的方案是唯一的.
$\therefore$方案数的上界也是$2^{n - \vert \mathfrak{B}\vert}$
//此代码是已知第 k 小的结果，求 k
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lb;
const int maxn=100007;
ll p[maxn],n,cnt;
inline ll ksc(ull x,ull y,ll p) //O(1)快速乘（防爆ll）
{
return (x*y-(ull)((lb)x/p*y)*p+p)%p;
}
inline ll fastPow(ll a,ll k,ll p)// a 底数， k 指数， 求 a^k mod p
{
ll res = 1;
a%=p;
while(k > 0)
{
if (k & 1) res =ksc(res,a,p);
a = ksc(a,a,p);
k >>= 1;
}
return res;
}
inline void add(ll x)
{
for(ll i=32; i>=0; i--)
{
if(x&(1ll<<i))
{
if(!p[i])
{
p[i]=x,cnt++;
break;
}
else x^=p[i];
}
}
}
void work()//处理线性基
{
for(ll i=1; i<=32; i++)
for(ll j=1; j<=i; j++)
if(p[i]&(1ll<<(j-1)))p[i]^=p[j-1];
}
ll k_th(ll Q)
{
if(Q==0)return 1;//空集是第一个
work();
ll k=0,bit=1;
for(int i=0; i<=32; i++)
if(p[i])//根据二进制分解的方式来判断是线性基的解集中的顺序
{
if((Q&(1ll<<i)))
k+=bit;
bit<<=1;
}
return (k*fastPow(2,n-cnt,10086)+1)%10086;
}
int main()
{
ll t,Q;
cin>>n;//输入序列个数
for(ll i=1; i<=n; ++i)
{
cin>>t;//输入序列内容
add(t);
}
cin>>Q;//输入查询数字
cout<<k_th(Q);//返回查询位次
return 0;
}
