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的方法。

结论:每个数都出现一样的次数,且这个次数为 $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}$。这就完成了证明。

程序

#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;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注