自动搬运

查看原文

来自洛谷，原作者为

	Kinandra :D

搬运于2025-08-24 22:04:45，当前版本为作者最后更新于2019-01-30 14:26:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

.标签：线性基.

.首先求出$V$的线性基 $\mathfrak{B}$.

.如果去除序列$B$中重复的数, 使用线性基, 根据$Q$的二进制位便可以确定$Q$的排名, 可是如果不去重, 怎么才能知道每个数出现多少次呢?

.结论: 每个数都出现一样的次数, 且这个次数为$2^{n - \vert\mathfrak{B}\vert}$.

证明：所有不在线性基中的数的个数为$n-\vert\mathfrak{B}\vert$, 我们任意选择它的一个子集$S$.

$\because\forall v \in S$, 有唯一的方式表达为$\mathfrak {B}$中向量的线性组合, 即$\mathfrak {B}$有唯一子集使得该子集中的向量异或和与$v$异或得$0$.

$\therefore\forall x\in B$, 我们都能找到$2^{n - \vert \mathfrak{B}\vert}$种不同的选择方案, 使得异或值为$x$.

又$\because$对于每个子集$S$, 选择线性基中的向量的方案是唯一的.

$\therefore$方案数的上界也是$2^{n - \vert \mathfrak{B}\vert}$.

有理有据, 令人信服

#include <iostream>
#include <cstdio>
using namespace std;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

int b[102];
int cnt = 1, mod = 10086;
void ist(int tmp) {
    for (int i = 30; i >= 0; --i) {
        if (!((1 << i) & tmp)) continue;
        if (!b[i]) {
            b[i] = tmp;
            break;
        }
        tmp ^= b[i];
        if (tmp == 0) {
            (cnt <<= 1) %= mod;
            break;
        }
    }
}


int dp[102][3];
int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int tmp = read();
        ist(tmp);
    }

    int tmp = read();
    int rk = 0;
    int tp = 1;
    for (int i = 0; i <= 30; ++i) {
        if (b[i]) {
            if ((tmp >> i) & 1)rk += tp;
            tp <<= 1;
        }
    }
    rk %= mod;
    printf("%d\n", (rk * cnt + 1) % mod);
    return 0;
}