题目

源地址：

http://acm.hdu.edu.cn/showproblem.php?pid=5088

理解

给你N堆石子，你可以除去其中的某些堆（也可以不除），问你能否使得后手必胜。 这是一道看起来像博弈的数学题，因为我们都知道如果想使得后手必胜，就只需要使得每一堆石子数的异或和为0即可。也就是说，我们只需要找出其中的某一些，他们的异或和为0，然后剩下的全都除去。如果能找到，输出Yes；找不到，说明不存在，输出No。

又由于异或的性质，我们可以知道在[1,pow(2,n)]中的任意多个数的异或和的情况至多有n种。显然的，如果情况数小于n，根据容斥定理我们可以知道，必定会存在至少两个数的值相等。根据异或的公式a^a=0，我们可以让两个相等的数进行异或，就得到了0，说明存在这样的选择方案。那么这个问题就转变了求n个数的异或和的情况数量。 我们可以把每一个数用二进制进行表示，可以发现，两个数异或的过程实际上就是对应二进制位进行消去的过程。我们可以看到，对于每一列，只要有1存在，那么就一定可以对这两个数进行异或，从而使得其中一个对应位置上变为0。也就是说，异或和的情况数量与这个二进制矩阵的秩的大小是等价的。那么问题就转换成了如何求解一个二进制矩阵的秩。分析到了这里，我们不难想到可以运用高斯消元对这个二进制矩阵进行处理。

本题的想法来自我的学长——Sio_Five 在具体的实现上，学长很多处理让我觉得非常惊艳。

  • 10^10大概是2^40左右，保险起见开到了65。根据前面我们推出的性质，异或和的情况最多只有65种（其实不可能会有这么多），所以，只要n大于65，一定输出Yes。
  • 在高斯消元的过程中，使用xor来代替先判断再消去，姿势更加优美。
  • 运用右移再&1的方法获取这一位的二进制值，比循环中/=2优雅多了。

代码

const int maxn = 1010;
const int maxm = 65;
int t, n;
ll a[maxn];
int mat[maxm][maxm];

int rnk(int mat[][maxm], int n, int m)
{
    int ret = 0;
    for (int i = 0, it = 0; i < n && it < m; ++it)
    {
        int pos = -1;
        for (int j = i; j < n; ++j)
        {
            if (mat[j][it])
            {
                pos = j;
                break;
            }
        }
        if (pos == -1)   continue;
        ++ret;
        if (pos != i)
        {
            for (int j = it; j < m; ++j)
            {
                swap(mat[i][j], mat[pos][j]);
            }
        }
        for (int j = 0; j < n; ++j)
        {
            if (i != j && mat[j][it])
            {
                for (int k = it; k < m; ++k)
                {
                    mat[j][k] ^= mat[i][k];
                }
            }
        }
        ++i;
    }
    return ret;
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        ll sum = 0;
        memset(mat, 0, sizeof(mat));
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
        {
            scanf("%I64d", &a[i]);
            sum ^= a[i];
        }
        if (sum == 0 || n > maxm)
        {
            printf("Yes\n");
            continue;
        }
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < maxm; ++j)
            {
                mat[i][j] = (a[i] >> j) & 1;
            }
        }
        int ret = rnk(mat, n, maxm);
        if (ret < n)  printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

更新日志

  • 2015年8月17日 已AC