bzoj2844albus就是要第一个出场解题报告

题意

给出n个数，在这n个数中选任意多的数进行异或，共产生了2ⁿ个含重复数字的数，现给出一个数q，问若将q插入这2ⁿ个数中，q是第几小的

算法分析

先对着n个数进行高斯消元，得到m个非零数和n-m个0，那m个非零的值就可组成2ⁿ种数，每个重复2^n-m次。只要按位统计q在其中排在第几位就可以了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
const int nn=100005;
const int MOD=10086;
int s[nn];
bool f[50];
int n,m,q;
inline int gauss(int n){
    int j(0), k;
    for (int i=30;i>=0;--i)
    {
            for (k = j;k < n;++k){
                if ((s[k] >> i) & 1){
                    break;
                }
            }
            if (n == k) continue;
            int t;
            t = s[j]; s[j] = s[k]; s[k] = t;
            for (int k=0;k<n;++k)
                if (k != j && ((s[k] >> i) & 1)) s[k] ^= s[j];
        ++j;
    }
    return j;
}
 
int main(){
    freopen("bzoj2844.in", "r", stdin);
    freopen("bzoj2844.out", "w", stdout);
    scanf("%d", &n);
    for (int i=0;i<n;++i) scanf("%d", &s[i]);
    memset(f, false, sizeof(f));
    q=gauss(n);
    long long p=0;
    scanf("%d", &m);
    int now=0;
    for (int i=0;i<q;++i)
    {
        long long st = 1 << (q - i - 1);
        if ((now ^ s[i]) <= m){
            p += st;
            now ^= s[i];
            if (now == m) break;
        }
    }
    long long c=1;
    for (int i=0;i<(n-q);++i) c = (c << 1) %MOD;
    p = (p * c + 1) % MOD;
    printf("%lld\n", p);
    fclose(stdin);
    fclose(stdout);
    return 0;
}