题目链接

题意

给定\(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\n", (lb.rank(q) % mod * num % mod + 1) % mod);

    return 0;

}