更多线性基知识戳这里

自认为讲得比较清楚的证明 qwq。

一个结论：$n$ 个数组成大小为 $s$ 的线性基，则能构成 $2^s$ 种不同的数，每个数出现 $2^{n-s}$ 次。

证明：首先每个不在线性基中的数都能被唯一地表示成若干线性基中的数异或和的形式。

考虑一个可以被线性基表示的数 $x$，将线性基划分为用来表示 $x$ 的数 $S1$、不用于表示 $x$ 的数 $S2$ 两个集合。那么对于每一个不在线性基中的数 $y$，将其表示为 $S1$ 的一个子集 $s1$ 与 $S2$ 的一个子集 $s2$（均可以为空）的异或和。那么就有选 $s1$（方案 $1$）或选 $s2$ 和 $y$（方案 $2$）两种选法。每个 $y$ 的选择之间相互独立，所以共 $2^{n-s}$ 种选法。

对于相互独立这一点可能存在疑问。比如当 $y_1$ 对应的 $s1$ 和 $y_2$ 对应的 $s1$ 之间有交集时，我们已经钦定了 $y_1$ 选方案 $2$，$y_2$ 对应的 $s1$ 集合就不能被完整选到。看起来有点凉，但是其实 $y_1$ 已经贡献完了交集部分，$y_2$ 只需要把其对应的 $s1$ 集合的不属于交集部分的数选上就可以了，也是能做到的。所以选择相互独立。

然后这道题就差不多做完了。

实现上，我们知道线性基可以通过被改造使得 $\forall_{i<j}\ (p_i\ xor \ p_j>p_i)\land (p_i\ xor\ p_j>p_j)$，且改造后线性基中有值的位置不变，所以可以直接记录每个有值的位置 $pos$ 及线性基中比它小的位置上有值的位置个数 $cnt$，枚举每个满足 $k$ 在二进制第 $pos$ 位有值的位置作为最高的不选位置，剩下更低位随便选，方案数 $2^{cnt}$。这样得到不可重集中 $k$ 的排名就可以知道可重集中 $k$ 的排名了。时间复杂度 $O(n\log V)$，其中 $V$ 为值域。

upd：感谢

#include<bits/stdc++.h>
#define ll long long
#define rep(i,s,e) for(int i=(s);i<=(e);++i)
#define Rep(i,s,e) for(int i=(e);i>=(s);--i)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=1e5+5,mod=10086;
int n,p[35],a[N],k,b[N];
inline void ins(int x){
	Rep(i,0,30) if(x&(1<<i)){
		if(!p[i]) return p[i]=x,void();
		x^=p[i];
	}
}
inline int ksm(int x,int y){
	int res=1;
	for(;y;y>>=1){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
signed main(){
	n=read();
	rep(i,1,n) a[i]=read(),ins(a[i]);
	int s=0,rk=0;
	rep(i,0,30) if(p[i]) b[s++]=i;
	k=read();
	rep(i,0,s-1) if(k&(1<<b[i])) rk|=(1<<i);
	rk=1ll*ksm(2,n-s)*rk%mod;
	printf("%d\n",(rk+1)%mod);
}