Chlience

【题解】BZOJ 2844 albus就是要第一个出场
Problem给定 $n$ 个元素的集合 $S$ ,将其子集异或和从小到大排序,问 $x$ 第一次出现的位置Tho...
扫描右侧二维码阅读全文
24
2019/01

【题解】BZOJ 2844 albus就是要第一个出场

Problem

给定 $n$ 个元素的集合 $S$ ,将其子集异或和从小到大排序,问 $x$ 第一次出现的位置

Thought

首先,肯定是从小到大选择
要表示出某个数,利用基中的元素有且仅有一种方法
然后瞎选其他的元素然后用基去抵消一共有 $2^{n-|B|}$ 种方法

设 $x$ 在不重复中为第 $k$ 小,那么答案为 $(k- 1) * 2^{n-|B|}+1$

线性基一共能表示 $2^{|B|}$ 个元素
每次从大到小和线性基中的元素进行对比,即可算出其为第 $k$ 小

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = 31;
const int mod = 10086;
int a[N], b[N];
int bin[M];
int n, len, maxa, q, cnt, Rank;
int f[M];
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void getLen() {
    for(int i = 1; i < M && !len; ++ i)
        if(maxa < bin[i])
            len = i;
}
void getBasis() {
    for(int i = 1; i <= n; ++ i)
        for(int j = len; j; -- j) {
            if(a[i] & bin[j - 1]) {
                if(b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for(int k = 1; k < j; ++ k)
                        if(b[j] & bin[k - 1])
                            b[j] ^= b[k];
                    for(int k = len; k > j; -- k)
                        if(b[k] & bin[j - 1])
                            b[k] ^= b[j];
                    break;
                }
            }
        }
}
int qpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * a * ans % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
void getRank(int key) {
    Rank = 0; cnt = 0;
    for(int i = 1; i <= len ; ++ i)
        if(b[i] & bin[i - 1])
            f[++ cnt] = b[i];
    for(int i = cnt; i; -- i) {
        if(key >= f[i]) {
            Rank += bin[i - 1];
            key ^= f[i];
        }
    }
    printf("%lld\n", (1ll * Rank * qpow(2, n - cnt) % mod + 1) % mod);
}
int main() {
    bin[0] = 1;
    for(int i = 1; i < M; ++ i) bin[i] = bin[i - 1] << 1;
    n = read();
    for(int i = 1; i <= n; ++ i) {
        a[i] = read();
        maxa = max(maxa, a[i]);
    }
    getLen();
    getBasis();
    getRank(read());
    return 0;
}
Last modification:January 24th, 2019 at 07:11 pm

Leave a Comment