[bzoj 2844] albus就是要第一个出场

求n元可重集不去重的异或空间中x的最小排名模10086的值 (额外加一个0, 排名从1开始标号). (1≤n≤10^5, 其他所有数不超过10^9) Gauss-Jordan消元, 然后从高位向低位一边凑出x (或者说把x消成0), 一边统计有多少个数小于x, 最后加1即可. 怎样判断凑x是否需要异或上a[i]呢? 由于线性基已从大到小排序, 且最高位的1仅出现在一个数上, 比一比a[i]和x的大小即可.

去不去重, 区别仅在于是否考虑消元消出的0的贡献.

上述均正确, 但是如果要给个证明, 暂时说不清道不明......

const int MOD = 10086, N = 1e5;
int a[N], pow2[N+1], now;

void gauss_jordan(int n)
{
	for (int x = 1<<29; x && now < n; x >>= 1) {
		int r = now;
		while (r < n && !(a[r] & x)) ++r;
		if (r == n) continue;
		swap(a[r], a[now]);
		Rep (i, 0, n) if (i != now && (a[i] & x)) a[i] ^= a[now];
		++now;
	}
}

int solve(int n, int x)
{
	int* p = pow2 + n - 1, ans = 1;
	Rep (i, 0, now) {
		if (a[i] <= x) {
			(ans += *p) %= MOD;
			x ^= a[i];
		}
		--p;
	}
	return ans;
}

int main()
{
	int n;
	scanf("%d", &n);
	pow2[0] = 1;
	Rep (i, 0, n) {
		scanf("%d", &a[i]);
		pow2[i+1] = pow2[i] * 2 % MOD;
	}
	gauss_jordan(n);
	int x;
	scanf("%d", &x);
	printf("%d\n", solve(n, x));
	return 0;
}