学习线性基

参考博客：

https://blog.csdn.net/a_forever_dream/article/details/83654397

https://ouuan.github.io/%E7%BA%BF%E6%80%A7%E5%9F%BA%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

https://blog.sengxian.com/algorithms/linear-basis

线性基性质：

1、原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
2、线性基里面的任意一些数异或起来都不能得到0 00
3、线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

解决的问题

1、最大异或和

2、第

3、求所有异或值的和

【例题】P3812 【模板】线性基

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int M = 70;
 5 typedef struct LB{
 6     ll d[M];
 7     void Insert( ll x ){
 8         ll t = x ;
 9         for(ll i=62;i>=0;i--){
10             if( (x & (1ll<<i))  ){
11                 if( d[i] ){
12                     x ^= d[i];
13                 }else {
14                     d[i] = x;
15                     break;
16                 }
17             }
18         }
19     }
20     ll Max(){
21         ll ans = 0 ;
22         for(int i=62;i>=0;i--){
23             ans = max( ans , ans ^ d[i] );
24         }
25         return ans;
26     }
27 }LB;
28 LB s;
29 int n;
30 ll a[M];
31 int main()
32 {
33     scanf("%d",&n);
34     for(int i=1;i<=n;i++){
35         scanf("%lld",&a[i]);
36         s.Insert(a[i]);
37     }
38 
39     return printf("%lld
",s.Max())*0;
40 }

View Code

【例题】P4570 [BJWC2011]元素

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int M = 70;
 5 const int N = 1e3+10;
 6 typedef struct Node {
 7     ll No;
 8     ll val;
 9     bool operator < ( const Node & rhs) const {
10         return val > rhs.val;
11     }
12 }Node ;
13 Node a[N];
14 typedef struct LB{
15     ll d[M];
16     bool Insert( ll x ){
17         for(int i=62;i>=0;i--){
18             if( (1ll<<i) & x ){
19                 if(d[i]){
20                     x ^= d[i];
21                 }else{
22                     d[i] = x ;
23                     return true;
24                 }
25             }
26         }
27         return false ;
28     }
29 
30 }LB;
31 LB s;
32 int n;
33 int main()
34 {
35     scanf("%d",&n);
36     for(int i=1;i<=n;i++){
37         scanf("%lld%lld",&a[i].No,&a[i].val);
38     }
39     sort( a+1 , a+1+n );
40     ll ans = 0 ;
41     for(int i=1;i<=n;i++){
42         if( s.Insert(a[i].No) )
43             ans += a[i].val;
44     }
45     return printf("%lld
",ans)*0;
46 }

View Code

【例题】P3857 [TJOI2008]彩灯

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 100;
 5 char s[N][N];
 6 ll a[N];
 7 int n,m;
 8 struct LB{
 9     ll d[70];
10     bool Insert( ll x ){
11         for(int i=62;i>=0;i--){
12             if( (x>>i)&1 ){
13                 if(!d[i]){
14                     d[i] = x ;
15                     return true;
16                 }else{
17                     x ^= d[i] ;
18                 }
19             }
20         }
21         return false ;
22     }
23 }S;
24 int main()
25 {
26     scanf("%d%d",&m,&n);
27     for(int i=1;i<=n;i++){
28         scanf("%s",s[i]);
29     }
30     for(int i=1;i<=n;i++){
31 
32         for(int j=m-1;j>=0;j--){
33             a[i] = a[i]+ (1ll*(s[i][j]=='O')<<(m-1-j)) ;
34         }
35         //printf("%lld
",a[i]);
36     }
37     int k = 0 ;
38     for(int i=1;i<=n;i++){
39         if( S.Insert(a[i]) )
40             k++;
41     }
42 
43     ll ans = 1 ;
44     for(int i=1;i<=k;i++){
45         ans = (ans<<1) % 2008 ;
46     }
47     printf("%lld
",ans);
48     return 0;
49 }

View Code

【例题】P3292 [SCOI2016]幸运数字

  1 // luogu-judger-enable-o2
  2 #include<cstdio>
  3 #include<cctype>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 typedef long long ll;
  8 const int N = 20010;
  9 const int M = 60 ;
 10 
 11 template < class T >
 12 void read( T& x ){
 13     x = 0;
 14     int f = 1 ;
 15     char c = getchar() ;
 16     while(  c<'0'||c>'9' ) {
 17         if (c == '-') f = -1;
 18         c = getchar();
 19     }
 20     while( c>='0'&&c<='9' ) {
 21         x = x * 10 + c - '0';
 22         c = getchar();
 23     }
 24     x = x * f ;
 25 }
 26 inline ll max( ll x,ll y ){
 27     return x > y ? x : y ;
 28 }
 29 typedef struct Edge {
 30     int to , next ;
 31 }Edge ;
 32 Edge e[N<<1] ;
 33 int n,Q,head[N],cnt;
 34 
 35 inline void add_edge(int u,int v){
 36     e[ cnt ] = Edge{ v , head[u] };
 37     head[u] = cnt ++ ;
 38 }
 39 
 40 ll G[N],p[N][16][M+1],Ans[M+1]; //价值，树上线性基，答案线性基
 41 int up[N][16],dep[N] ; //前缀第2^k个 和 深度
 42 
 43 inline void Insert( ll x ){
 44     for(int i = M ; ~i ; i-- ){
 45         if( x >> i ){
 46             if( !Ans[i] ) { Ans[i] = x ; break ; }
 47             else x ^= Ans[i] ;
 48         }
 49     }
 50 }
 51 inline void Insert( int u , int d , ll x ){
 52     for(int i = M ; ~i ; i-- ){
 53         if( x >> i ){
 54             if( !p[u][d][i] ) { p[u][d][i] = x ; break; }
 55             else x ^= p[u][d][i] ;
 56         }
 57     }
 58 }
 59 
 60 void dfs(int u,int Fa){
 61     dep[u] = dep[Fa] + 1 ;
 62     up[u][0] = Fa ;
 63 
 64     Insert( u , 0 , G[u] );
 65 
 66     for(int i=1 ; i <= 15 ; i++ ){
 67 
 68         up[u][i] = up[up[u][i-1]][i-1];   // 爸爸的爸爸是爷爷
 69 
 70         if( !up[u][i] )  break;         // 因为根结点为虚点0
 71 
 72         for( int j=M ; ~j ; j-- ){
 73             if( p[u][i-1][j] ) Insert( u , i , p[u][i-1][j] );
 74             if( p[up[u][i-1]][i-1][j] ) Insert( u , i ,p[up[u][i-1]][i-1][j] );
 75         }
 76     }
 77     for( register int i = head[u] ; ~i ; i=e[i].next ){
 78         if( e[i].to != Fa ) dfs( e[i].to , u ) ;
 79     }
 80 }
 81 ll query ( int u , int v ){
 82     memset( Ans , 0 , sizeof Ans );     //对于多次询问，清空线性基
 83 
 84     if( dep[u] < dep[v] ) swap(u, v);   //默认u为更低点
 85 
 86     for(int i=15;~i;i--){               //利用二进制的想法，爬到同一高度
 87         if( dep[up[u][i]] >= dep[v] ){  //同时把对爬高的过程，对应结点的值插入线性基
 88             for(int j=M;~j;j--)
 89                 if( p[u][i][j] ) Insert( p[u][i][j] );
 90             u = up[u][i] ;
 91         }
 92     }
 93 
 94     if( u^v ){          //对于不同的位置来说，需要大家同时迈步走
 95         for(int i=15;~i;i--){
 96             if( up[u][i] != up[v][i] ){ //双方都把对应的结点位置的值，插入答案线性基
 97                 for(int j=M;~j;j--){
 98                     if( p[u][i][j] ) Insert( p[u][i][j] );
 99                     if( p[v][i][j] ) Insert( p[v][i][j] );
100                 }
101                 u = up[u][i] , v = up[v][i];
102             }
103         }
104         Insert(G[u]), Insert(G[v]), Insert(G[up[u][0]]);
105     }else Insert(G[u]);
106 
107     ll res = 0;
108     for(int j=M ; ~j ;j-- ){
109         res = max ( res , res^Ans[j] );
110     }
111     return res ;
112 }
113 
114 int main(){
115     memset( head,-1,sizeof head );
116     read(n) , read(Q) ;
117     for( register int i=1 ; i<=n;i++ ) read(G[i]);
118     int u,v ;
119     for( register int i=1 ; i^n ;i++ ) {
120         read(u) , read(v) ;
121         add_edge(u, v), add_edge(v, u);
122     }
123     dfs(1, 0);
124 
125     while( Q-- ){
126         read(u), read(v) ;
127         printf("%lld
",query(u,v));
128     }
129     return 0 ;
130 }
131 
132 /*
133  *
134 4 2
135 11 5 7 9
136 1 2
137 1 3
138 1 4
139 2 3
140 1 4
141 
142 14
143 11
144  */

View Code