ACM学习历程—HDU 3949 XOR（xor高斯消元）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3949

题目大意是给n个数，然后随便取几个数求xor和，求第k小的。（重复不计算）

首先想把所有xor的值都求出来，对于这个规模的n是不可行的。

然后之前有过类似的题，求最大的，有一种方法用到了线性基。

那么线性基能不能表示第k大的呢？

显然，因为线性基可以不重复的表示所有结果。它和原数组是等价的。

对于一个满秩矩阵

100000

010000

001000

000100

000010

000001

可以看出来最小的就是1，次小的是2，后面以此就是3，4，5，6....2^6-1.

可以看出来，每个向量基，都有取或者不取两种选择，而且把k二进制拆开来后，第i位就表示第i小的向量基取不取（1取，0不取）。

因为保证了第k大的基总大于比他小的基的线性组合。

此外，需要对非满秩的矩阵进行特判。因为其存在0的结果，如果要求最小，那么就是0。如果不是，那么就是求当前矩阵下的第(k-1)小。

然后接下来求的时候，需要对不存在的情况特判，因为每个数都有取或不取，即2^row-1种，除去全不取的情况。

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <string>

#define LL long long

using namespace std;

//xor高斯消元求线性基

//时间复杂度O(63n)

const int maxN = ;

LL a[maxN];

int n;

int xorGauss(int n)//可以用来解模二的方程，加快速度

{

    int row = ;

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

    {

        int j;

        for (j = row; j < n; j++)

            if(a[j]&((LL)<<i))

                break;

        if (j != n)

        {

            swap(a[row], a[j]);

            for (j = ; j < n; j++)

            {

                if(j == row) continue;

                if(a[j]&((LL)<<i))

                    a[j] ^= a[row];

            }

            row++;

        }

    }

    return row;

}

void input()

{

    scanf("%d", &n);

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

        scanf("%I64d", &a[i]);

}

LL findK(int row, int k)

{

    if (row < n)

    {

        if (k == )

            return ;

        else k--;

    }

    if (k >= (LL)<<row)

        return -;

    LL ans = ;

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

    {

        if (k&((LL)<<i))

            ans ^= a[row-i-];

    }

    return ans;

}

void work()

{

    int row, q;

    LL k, ans;

    row = xorGauss(n);

    scanf("%d", &q);

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

    {

        scanf("%I64d", &k);

        ans = findK(row, k);

        printf("%I64d\n", ans);

    }

}

int main()

{

    //freopen("test.in", "r", stdin);

    int T;

    scanf("%d", &T);

    for (int times = ; times < T; ++times)

    {

        printf("Case #%d:\n", times+);

        input();

        work();

    }

}