BZOJ 2844 albus就是要第一个出场 高斯消元+线性基

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
#define MO 10086
using namespace std;

int cnt,m;
int a[MAX],k,b[MAX];

void Gauss()
{
	k = cnt;
	for(int i = 1; i <=  cnt; ++i) {
		for(int j = i + 1; j <= cnt; ++j)
			if(a[j] > a[i])
				swap(a[i],a[j]);
		if(!a[i]) {
			k = i - 1;
			break;
		}
		for(int j = 31; ~j; --j)
			if((a[i] >> j)&1) {
				b[i] = j;
				for(int k = 1; k <= cnt; ++k)
					if(k != i && (a[k] >> j)&1)
						a[k] ^= a[i];
				break;
			}
	}
}

inline int Power(int x,int y)
{
	int re = 1;
	while(y) {
		if(y&1)	re = re * x % MO;
		x = x * x % MO;
		y >>= 1;
	}
	return re;
}

int main()
{
	cin >> cnt;
	for(int i = 1; i <= cnt; ++i)
		scanf("%d",&a[i]);
	cin >> m;
	Gauss();
	int ans = 1;
	for(int i = 1; i <= k; ++i)
		if((m >> b[i])&1) {
			m ^= a[i];
			ans = (ans + Power(2,cnt - i)) % MO;
		}
	cout << ans << endl;
	return 0;
}