【BZOJ 2844】albus就是要第一个出场

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2844
数据生成器：http://paste.ubuntu.com/23312434/

话说这个题啊！还是挺有意思哒！
有一个结论：如果相同的数要计入答案的话，那每种答案出现了2^(n-线性基的数量)
证明：既然都为0了，那么取不取都不影响答案，于是可以随便搞一搞

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 10086;
const int N = 100000+9;
const int SGZ = 30+9;

int n,m,arr[N],bas[SGZ],cnt,vout;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool insert(int w) {
	for (int i=30;~i;i--) if (w&(1<<i)) {
		if (bas[i]) {
			w ^= bas[i];
		} else {
			bas[i] = w;
			return true;
		}
	}
	return false;
}

inline int pow(int w , int t) {
	int ret = 1;
	while (t) {
		if (t&1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		arr[i] = read();
		cnt += insert(arr[i]);
	}
	m = read();
	for (int i=30,tmp=pow(2,n-cnt);~i;i--) if (bas[i]) {
		cnt--;
		if (m&(1<<i)) {
			vout += tmp * (1LL<<cnt) % MOD;
			vout %= MOD;
		}
	}
	printf("%d\n",(vout+1)%MOD);
	return 0;
}