HDU 3949 XOR [高斯消元XOR 线性基]

题意：

给你 N个数，从中取出若干个进行异或运算，求最
后所有可以得到的异或结果中的第k小值

N个数高斯消元求出线性基后，设秩为$r$，那么总共可以组成$2^r$中数字(本题不能不选，所以$2^r -1$)

然后如果$k \ge 2^r$就不存在啦

否则一定可以有$k$小，因为现在$1..r$行每行都有一位是1(左面是最高位)

从高到低枚举k的二进制，如果是1就异或上对应的行就行了，最后就是k小值啦

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bitset>

using namespace std;

typedef long long ll;

const int N=1e4+,INF=1e9;

inline ll read(){

    char c=getchar();ll x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q;

ll a[N],k,bin[N];

void ini(){

    bin[]=;for(int i=;i<=;i++) bin[i]=bin[i-]<<;

}

int now;

void Gauss(){

    now=;

    for(int i=;i>=;i--){

        int j=now;

        while(j<=n&&!(a[j]&bin[i])) j++;

        if(j==n+) continue;

        if(j!=now) swap(a[j],a[now]);

        for(int k=;k<=n;k++)

            if(k!=now&&(a[k]&bin[i])) a[k]^=a[now];

        now++;

    }

    now--;

}

ll Query(ll k){//printf("Q %lld\n",k);

    ll ans=;

    if(now!=n) k--;

    if(k>=bin[now]) return -;

    for(int i=;i<=now;i++)

        if(k&bin[now-i]) ans^=a[i];

    return ans;

}

int main(){

    freopen("in","r",stdin);

    ini();

    int T=read(),cas=;

    while(T--){printf("Case #%d:\n",++cas);

        n=read();

        for(int i=;i<=n;i++) a[i]=read();

        Gauss();

        Q=read();

        while(Q--) printf("%lld\n",Query(read()));

    }

}

秒客网

HDU 3949 XOR [高斯消元XOR 线性基]

相关文章