题意
给定一个长度为 \(n\) 的序列 \(A\)，设可重集合 \(S=\left\{\operatorname{xor}_{i=1}^nA_ix_i\mid x_i\in\{0,1\}\right\}\)，即 \(S\) 为 \(A\) 的所有子集的异或和构成的集合。
给定一个数 \(k\)，求 \(k\) 在 \(S\) 中的排名。如果 \(S\) 中有多个 \(k\)，取最小的排名。
\(1\le n\le10^5\)，其他输入不超过 \(10^9\)。
思路
首先构造 \(A\) 的线性基 \(B\)，设 \(\operatorname{span}(B)=\operatorname{span}(A)=S\)。由于可以一个数都不选，所以 \(0\in S\)。
如果集合 \(S\) 不可重，给定一个数 \(k\)，如何求出它在 \(S\) 中的排名？保证 \(k\) 在 \(S\) 中出现。
我们从低到高考虑每一位。如果 \(B_i\) 不为空，并且 \(k\) 的第 \(i\) 位为 \(1\)，说明我们需要取出 \(B_i\) 以构造出 \(k\)。根据线性基的性质，\(B_i\) 的高位为 \(0\)，且 \(B\) 中其他数的第 \(i\) 位为 \(0\)，所以必须取出 \(B_i\)，且取出 \(B_i\) 不影响之前和之后的操作。至于其他没考虑到的位，由于保证可以构造出 \(k\)，因此可以不用管。
求排名 \(rk\) 的具体代码如下：
int rk = 0, pw = 1;
f(i, 0, 30) if (B[i]) {
if (k >> i & 1) rk += pw;
pw <<= 1;
}
取出第 \(i\) 个线性基，对应的贡献是 \(2^{i-1}\)。可以对照一个例子：
- 线性基为 \(\{00100,01001,10011\}\)，能构造出的数的集合为 \(\{00100,01001,01101,10011,10111,11010,11110\}\)。
现在考虑集合 \(S\) 可重的情况。设 \(f(s)=\operatorname{xor}_{s}x\)，其中 \(s\) 为某个集合。
考虑插入线性基的过程，插入线性基失败即是出现了重复。
设一个插入线性基失败的数为 \(x\)，那么存在 \(B'\subseteq B\) 使得 \(f(B')\operatorname{xor}x=0\)。设 \(x\) 对应的 \(B'\) 为 \(B_x\)。
根据异或的性质，如果用线性基中的数能构造出 \(y\)，设 \(y=f(Y)\)（\(Y\subseteq A\)），那么 \(y\) 也等于 \(f(Y)\operatorname{xor}f(B_x)\operatorname{xor}x\)，其中 \(x\) 是某个插入线性基失败的数。
对于每个 \(y\)，用线性基中的数构造的方案是唯一的（否则不符合线性基的定义）；而 \(x\) 对应的 \(B_x\) 也是唯一的。因此对于每个 \(x\) 都可以用或不用，所以每个 \(y\) 的总方案数都要乘以 \(2^{n-|B|}\)。
于是答案为 \(rk\times2^{n-|B|}+1\)。
代码
\(2^{n-|B|}\) 可以在插入线性基的同时计算出来，这样就不需要用到快速幂了。
#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
int constexpr MOD = 10086;
int n, rk, pw = 1, B[32], c = 1;
void ins(int x) {
g(i, 30, 0) if (x >> i & 1) {
if (!B[i]) return B[i] = x, void();
x ^= B[i];
if (!x) return (c <<= 1) %= MOD, void();
}
return;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n;
int x;
f(i, 1, n) cin >> x, ins(x);
cin >> x;
f(i, 0, 30) if (B[i]) {
if (x >> i & 1) (rk += pw) %= MOD;
(pw <<= 1) %= MOD;
}
cout << (rk * c + 1) % MOD << '\n';
return 0;
}