bzoj 2844 albus就是要第一个出场 异或和出现次数 线性基

题目链接

题意

给定(n)个数，将其所有的子集（(2^n)个）的异或和按升序排列。给出一个询问(q)，问(q)在该序列中第一次出现位置的下标（下标从(1)开始）。

题解

结论

记其线性基为(mathfrak B)，则每个异或和出现的次数为(2^{n-|mathfrak B|}).

证明

从高斯消元的角度看，将(n)个数看作(n)个行向量，经行等价变换后得到一个行简化梯形矩阵，非零行的行数为(|mathfrak B|)，而下面的(n-|mathfrak B|)行为零行。

从上面的(|mathfrak B|)行中取若干行，异或起来得到一个值(x)；而在下面的(n-|mathfrak B|)行中无论取多少个与(x)进行异或，得到的值都仍为(x)（因为下面(n-|mathfrak B|)行的数均为(0)）. 因为一共有(2^{n-|mathfrak B|})种取法，所以值(x)出现了(2^{n-|mathfrak B|})次。

注意点

无论这(n)个数是否线性相关，(0)都始终在序列中出现，因为子集可以为空集。

进一步的，如果该(n)个数线性无关，则(0)只会出现一次，由线性无关的定义易知。
对应于上面的结论，因线性无关，所以(|mathfrak B|=n,2^{n-|mathfrak B|}=1)，也是吻合的。

Code

#include <bits/stdc++.h>
#define mod 10086
#define maxl 30
using namespace std;
typedef long long LL;
LL poww(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1) (ret *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return ret;
}
struct LinearBasis {
    LL a[maxl+1]; int size; vector<int> v;
    LinearBasis() { memset(a, 0, sizeof(a)); size = 0; v.clear(); }
    void insert(LL t) {
        for (int i = maxl; i >= 0; --i) {
            if (!(t >> i & 1)) continue;
            if (a[i]) t ^= a[i];
            else {
                ++size;
                for (int j = 0; j < i; ++j) if (t >> j & 1) t ^= a[j];
                for (int j = i+1; j <= maxl; ++j) if (a[j] >> i & 1) a[j] ^= t;
                a[i] = t;
                return;
            }
        }
    }
    void basis() {
        for (int i = 0; i <= maxl; ++i) if (a[i]) v.push_back(i);
    }
    LL rank(LL x) {
        LL ret = 0;
        for (int i = 0; i < v.size(); ++i) if (x >> v[i] & 1) ret += 1LL << i;
        return ret;
    }
};
int main() {
    int n, x, q;
    scanf("%d", &n);
    LinearBasis lb;
    for (int i = 0; i < n; ++i) scanf("%d", &x), lb.insert(x);
    lb.basis();
    scanf("%d", &q);
    LL num = poww(2, n - lb.size);
    printf("%lld
", (lb.rank(q) % mod * num % mod + 1) % mod);
    return 0;
}