Article From:https://www.cnblogs.com/xidian-mao/p/9688111.html
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
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
output
YES YES NO
1 #include <bits/stdc++.h> 2 #define N 30 3 using namespace std; 4 int b[N+5]; 5 int n; 6 int main () 7 { 8 scanf ("%d",&n); 9 for (int i=1;i<=n;i++) { 10 int x; scanf ("%d",&x); 11 for (int j=N;j>=0;j--) 12 if ((1<<j)&x) { 13 if (!b[j]) { 14 b[j]=x; 15 break; 16 } 17 else x^=b[j]; 18 } 19 } 20 int Q; scanf ("%d",&Q); 21 while (Q--) { 22 int x,y; scanf ("%d %d",&x,&y); 23 x=x^y; 24 for (int i=N;i>=0;i--) { 25 if ((1<<i)&x) 26 x^=b[i]; 27 } 28 if (x) printf("NO\n"); 29 else printf("YES\n"); 30 } 31 return 0; 32 }
Link of this Article: Linear basis of topic –XOR