Linear basis of topic –XOR

　　　I didn’t expect XOR to have an interesting connection with linear algebra.

           nThe number can be transformed into an upper triangular matrix (linearly independent?!!).

            

Link: https://www.nowcoder.com/acm/contest/180/D
Source: cattle net

Contents

• Title Description
• Input Description:
• Output Description:
  • • • Input example:
      • Output example:
• input
• output

Title Description

A has n numbers, and he asks a n interesting question: He wants to know if, for a N Y x, y, X can be changed to y by a N Y number of times or by a N Y number of times.

Input Description:

The first behavior is an integer n, which represents the number of elements.
Second lines and one line contain n integers, representing elements in a sequence respectively.
Third an integer Q, which indicates the number of inquiries.
Next, Q rows, each row has two numbers x, y, meaning as shown in the title.

Output Description:

Output Q line, if x can be converted to y, output "YES", otherwise output "NO".

Example 1

input

copy

5
1 2 3 4 5
3
6 7 
2 1
3 8

output

copy

YES
YES
NO

#include <bits/stdc++.h>
#define N 30
using namespace std;
int b[N+5];
int n;
int main ()
{
    scanf ("%d",&n);
    for (int i=1;i<=n;i++) {
        int x; scanf ("%d",&x);
        for (int j=N;j>=0;j--) 
            if ((1<<j)&x) {
                if (!b[j]) {
                    b[j]=x;
                    break;
                }
                else       x^=b[j];
            }
    }
    int Q; scanf ("%d",&Q);
    while (Q--) {
        int x,y; scanf ("%d %d",&x,&y);
        x=x^y;
        for (int i=N;i>=0;i--)  {
            if ((1<<i)&x) 
                x^=b[i];
        }
        if (x) printf("NO\n");
        else   printf("YES\n");
    }
    return 0;
}