题解 P4869 【albus就是要第一个出场】
Kinandra
·
·
题解
.标签：线性基.
.首先求出V的线性基 \mathfrak{B}.
.如果去除序列B中重复的数, 使用线性基, 根据Q的二进制位便可以确定Q的排名, 可是如果不去重, 怎么才能知道每个数出现多少次呢?
.结论: 每个数都出现一样的次数, 且这个次数为2^{n - \vert\mathfrak{B}\vert}.
证明：所有不在线性基中的数的个数为n-\vert\mathfrak{B}\vert, 我们任意选择它的一个子集S.
$\therefore\forall x\in B$, 我们都能找到$2^{n - \vert \mathfrak{B}\vert}$种不同的选择方案, 使得异或值为$x$.
又$\because$对于每个子集$S$, 选择线性基中的向量的方案是唯一的.
$\therefore$方案数的上界也是$2^{n - \vert \mathfrak{B}\vert}$.
有理有据, 令人信服
```cpp
#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;
}
```