hdu3949xor(高斯消元)

看了半天題，沒想出怎麼用高斯消元解題，看完别人ac明白。

首先，用二進制去看待每一個數，因為xor其實就是二進制的不進位加法。

比如 （十進制）2^0 2^1

1 1

2 1

3 1 1

其實3參與的xor可以用（1^2）代替，因為1 , 2 ,3線性相關。

是以需要做的就是求出這n個數的線性無關基，這是就是可以用高斯消元，但是要求的是第幾小 ，是以希望每個消元後的數都盡量小，是以應該從高位開始消元

不了解可以看一下下邊的資料（同樣n個數不同姿勢出來的結果）

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <stack>
#include <vector>
#include <string.h>
#include <queue>
#define msc(X) memset(X,-1,sizeof(X))
#define ms(X) memset(X,0,sizeof(X))
typedef long long LL;
using namespace std;
LL a[];
int n;
//求第幾小應該從最高位開始消元，這樣保證了線性無關組元素和最小
void Guass(void)
{
    int max_r,col,k;
    for(k=,col=;k<n&&col>=;col--)
    {
        max_r=k;
        for(int i=k+;i<n;i++)
            if(a[i]&(l<<col)) {
                max_r=i;
                break;
            }
        if((a[max_r]&(l<<col))==)
            continue;
        if(max_r!=k)
            swap(a[k],a[max_r]);
        for(int i=;i<n;i++)
            if(i!=k&&(a[i]&(l<<col)))
                a[i]^=a[k];
        k++;
    }
    sort(a,a+n);
    n=unique(a,a+n)-a;
}
LL cal(LL k)
{
    LL ans=;
    int i=;
    if(a[]==){
        if(k==) return ;
        k--;
        i++;
    }
    for(;i<n&&k;k>>=,i++)
        if(k&)
            ans^=a[i];
    if(i==n&&k) return -;
    return ans;
}
int main(int argc, char const *argv[])
{
    int t,ti=;
    scanf("%d",&t);
    while(++ti<=t){
        scanf("%d",&n);
        for(int i=;i<n;i++)
            scanf("%I64d",a+i);
        Guass();
        printf("Case #%d:\n",ti);
        int q;
        scanf("%d",&q);
        while(q--){
            LL k;
            scanf("%I64d",&k);
            printf("%I64d\n",cal(k) );
        }
    }
    return ;
}