[Nowcoder180D] xor序列 (线性基)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://www.nowcoder.com/acm/contest/180/D

题意就是给你$n$个数和$q$次询问，每次问你一个数$x$能不能被上述$n$个数之间随意异或得到。

这题可以想到构造一组32个异或方程的方程组，每一个方程代表数位中某一位的异或结果。我们需要判断这个方程组是否有解。考虑方程组有无解实际上就是判断这个方程组的参数矩阵构成的一组基底能否表示每次查询的$x$，因此我们可以用线性基的技术解决这个问题。

关于线性基可以学习这篇blog：https://blog.sengxian.com/algorithms/linear-basis

由于我们不关心这组方程中最大线性无关组具体是什么，因此我们可以直接向无关组中判断插入每一个方程（就是每一个数字）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

const int maxn = 33;
int n, q, x, y;
int a[maxn], b[maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d", &n)) {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    for(int i = 0; i < n; i++) {
      scanf("%d", &x);
      for(int j = 0; j < 31; j++) {
        if(x >> j & 1) {
          if(!a[j]) {
            a[j] = x;
            break;
          }
          x ^= a[j];
        }
      }
    }
    scanf("%d", &q);
    while(q--) {
      scanf("%d%d",&x,&y);
      x ^= y;
      memcpy(b, a, sizeof(a));
      for(int j = 0; j < 31; j++) {
        if(x >> j & 1) {
          if(!b[j]) {
            b[j] = x;
            break;
          }
          x ^= b[j];
        }
      }
      printf("%s\n", x == 0 ? "YES" : "NO");
    }
  }
  return 0;
}