跳转至

BZOJ2844 albus就是要第一个出场

题意

给定 n(n \le 10000)个数 a_1, a_2, \ldots, a_n 以及一个数 Q。将 a_1, a_2, \ldots, a_n 的所有子集（可以为空）的异或值从小到大排序得到序列 B，请问 Q 在 B 中第一次出现的下标是多少？保证 Q 在 B 中出现。

题解

这题也是我学习线性基时在Sengxian的博客上看到的例题。

由于Sengxian讲的已经非常好了，我就将重点部分贴上他的话吧。

这题要求某个数第一次出现的下标，也就相当于求它在线性基\mathfrak{B}中可以被张成的所有元素的排名，但是实际上应该求的是它在向量空间V中可以被张成的所有元素的排名。

一开始想到的应该都是前面一句话，如何求出这句话中提出的问题，实际上可以用类似于解决hdu3949的方法去像，首先肯定只有线性基上不为0的位才有贡献，于是我们从小到大枚举线性基上的数，如果当前位i上有数并且在Q中的对应的位上也有数，那么它肯定会大于所有该位为0的数（这里是指被张成的向量），于是就会有贡献2^{cnt}，其中cnt为从0位到i-1位对应的线性基中有数的有多少个位。

但是到这里只是解决了第一句话中的问题，它与第二句话中问题是有关联的，实际上只要把排名比Q小的数的重复次数算上去就行了，这里我是看的Sengxian的方法。

Quote

结论：每个数都出现一样的次数，且这个次数为 2^{n - \vert \mathfrak{B}\vert}。
证明：我们考虑在 B 中出现的任意一个数 x。所有不在线性基中的数的个数为 n - \vert \mathfrak{B}\vert，我们任意选择它的一个子集 S，对于 S 中的每个数 v，有唯一的方式表达为 \mathfrak {B} 中向量的线性组合。我们对于每个 v，将这个线性组合中的向量都选上（一个向量选多次不要紧），两个相同的数异或起来得到 0，所以对于每个数 x，我们都能找到 2^{n - \vert \mathfrak{B}\vert}种不同的选择方案，使得异或值为 x。又因为对于每个子集 S，为了使得最终异或值为 x，选择线性基中的向量的方案是唯一的，所以上界也是 2^{n - \vert \mathfrak{B}\vert}。这就完成了证明。

程序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 100007
#define MOD 10086
typedef long long ll;

ll N, Q;
ll a[MAX_N], b[32], c[32], top;

template <typename _T> inline void read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while (c < '0' || '9' < c) {
        if (c == '-') y = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
}

inline void makeBase () {
    for (int i = 1; i <= N; ++i)
        for (int j = 31; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k)
                        if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
                    for (int k = j + 1;k < 32; ++k)
                        if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
}

inline ll quick_pow (ll x, ll p) {
    ll ans = 1;
    while (p) {
        if (p & 1) (ans *= x) %= MOD;
        p >>= 1;
        (x *= x) %= MOD;
    }
    return ans % MOD;
}

int main () {
    read(N);
    for (int i = 1; i <= N; ++i) read(a[i]);
    read(Q);
    makeBase();
    ll res = 0;
    top = 0;
    for (int i = 0; i < 32; ++i)
        if (b[i]) {
            if (Q >> i & 1)
                (res += (1 << top)) %= MOD;
            top++;
        }
    res = res % MOD * quick_pow(2, N - top) % MOD + 1;
    printf("%lld\n", res % MOD);
    return 0;
}