求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;
}