线性基

•参考资料

[1]:算法 | 线性基学习笔记
[2]:线性基学习笔记

•理解

实数线性基就是n维空间的一个基底，

求线性基就是求他的基底，

也就是矩阵的最大线性无关组

可以用高斯消元来求。

异或线性基其实就是把一个数转化成二进制

转化成二进制后，最多的二进制位数就相当于他的维数

由于只有1和0，高斯消元的结果和异或的结果相同

故用异或来做可以把时间复杂度降到log

•习题

洛谷P3812 【模板】线性基 (求最大)

牛客xor序列 (查找)

洛谷P4570 [BJWC2011]元素 (插入/查找线性基不为0)

洛谷P4301 [CQOI2013]新Nim游戏 (插入/查找线性基不为0)

洛谷P3265 [JLOI2015]装备购买 (实数线性基)

hdu3494 XOR (第k大)

cf1100F (可以用来练习区间线性基，氮素会TLE_(:з」∠)_，正解是离线做法)

洛谷P4839 P哥的桶 (线性基+线段树)

2019牛客多校第一场A (异或和为0的所有子集长度和)

•初始线性基

 1 ll n;
 2 ll p[65];
 3 
 4 ///插入
 5 void Insert(ll x)
 6 {
 7     for(int i=60;i>=0;i--)
 8     {
 9         if(x&(1ll<<i))
10         {
11             if(!p[i])
12             {
13                 p[i]=x;
14                 break;
15             }
16             x^=p[i];
17         }
18     }
19 }
20 
21 
22 ///查找
23 bool Find(ll x)
24 {
25     for(int i=60;i>=0;i--)
26     {
27         if(x&(1ll<<i))
28         {
29             if(!p[i])
30             {
31                 p[i]=x;
32                 return true;
33             }
34             x^=p[i];
35         }
36     }
37     return false;
38 }
39 
40 
41 ///最大值
42 ll get_Max()
43 {
44     ll ans=0;
45     for(int i=60;i>=0;i--)
46         if(x&(1ll<<i))
47             ans=max(ans,ans^p[i]);
48     
49     return ans;
50 }
51 
52 
53 ///最小值
54 ll get_Min()
55 {
56     for(int i=0;i<=60;i++)
57         if(p[i])
58             return p[i];
59 }
60 
61 
62 ///第k大
63 ll cnt=0;
64 ll th[65];
65 void rebuild()
66 {
67     for(int i=60;i>=0;i--)
68         for(int j=i-1;j>=0;j--)
69             if(p[i]&(1ll<<j))
70                 p[i]^=p[j];
71 
72     for(int i=0;i<=60;i++)
73         if(p[i])
74             th[cnt++]=p[i];
75 }
76 ll kthquery(ll x)
77 {
78     if (x>=(1ll<<cnt))
79         return -1;
80     ll ans=0;
81     for(ll j=60;j>=0;j--)
82         if ((x&1ll<<j))
83             ans^=th[j];
84 
85     return ans;
86 }
87 
88 ///在求第k大时里面是包括 0 的
89 ///但是并不是所有的都可以异或出来 0 
90 ///如果构造出来的线性基有 k 位不为 1
91 ///那么说明每个数都提供了 1，则说明不会异或出 0 ，否则可以。
92 if(cnt!=n)
93     x--;
94 printf("%lld
", kthquery(x));

View Code

•例题

洛谷P4570 [BJWC2011]元素

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 int const maxn=1e5+5;
 5 struct node
 6 {
 7     ll no;
 8     ll val;
 9 }a[maxn];
10 ll pos[120];
11 bool cmp(node x,node y)
12 {
13     return x.val>y.val;
14 }
15 
16 bool Insert(ll x)
17 {
18     for(int i=105;i>=0;i--)
19     {
20         if(x&(1ll<<i))
21         {
22             if(!pos[i])
23             {
24                 pos[i]=x;
25                 return true;
26             }
27             else
28                 x^=pos[i];
29         }
30     }
31     return false;
32 }
33 
34 int main()
35 {
36     int n;
37     cin>>n;
38     for(int i=1;i<=n;i++)
39         cin>>a[i].no>>a[i].val;
40 
41     sort(a+1,a+1+n,cmp);
42 
43     ll ans=0;
44 
45     for(int i=1;i<=n;i++)
46     {
47         if(Insert(a[i].no))
48             ans+=a[i].val;
49     }
50     cout<<ans<<endl;
51 }

View Code

洛谷P3265 [JLOI2015]装备购买

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define eps 1e-5
 5 int const maxn=1e5+5;
 6 
 7 struct node
 8 {
 9     double m[550];
10     int v;
11 }a[550];
12 bool cmp(node x,node y)
13 {
14     return x.v<y.v;
15 }
16 
17 ll pos[200];
18 
19 int main()
20 {
21     int n,m;
22     cin>>n>>m;
23     for(int i=1;i<=n;i++)
24     {
25         for(int j=1;j<=m;j++)
26             cin>>a[i].m[j];
27     }
28 
29     for(int i=1;i<=n;i++)
30         cin>>a[i].v;
31     sort(a+1,a+1+n,cmp);
32 
33     ll ans=0;
34     int num=0;
35     for(int i=1;i<=n;i++)
36     {
37         for(int j=1;j<=m;j++)
38         {
39             if(abs(a[i].m[j])>eps)
40             {
41                 if(!pos[j])
42                 {
43                     pos[j]=i;
44                     num++;
45                     ans+=a[i].v;
46                     break;
47                 }
48                 else
49                 {
50                     ///高斯消元
51                     double x=a[i].m[j]/a[pos[j]].m[j];
52                     for(int k=j;k<=m;k++)
53                         a[i].m[k]-=a[pos[j]].m[k]*x;
54                 }
55             }
56         }
57     }
58     cout<<num<<' '<<ans<<endl;
59 }

View Code

•第k小

hdu3494 XOR

普通线性基是得到高斯消元后的矩阵

而求第k小需要得到最简化的行列式

这就是rebuild函数的作用，

最简化的每一行在th数组存放，

例如

1 3 4得到

$egin{bmatrix} 0&0 &1 \ 0&1 &1 \ 1&0 &0 end{bmatrix}$化简得$egin{bmatrix} 0&0 &1 \ 0&1 &0 \ 1&0 &0 end{bmatrix}$

按从小到大得

$th[0]=001_{2}=1_{10},th[1]=010_{2}=2_{10},th[2]=100_{2}=4_{10}$

一共有三个基向量，最多表示2³个数

求第3大，也就是第$011$大，需要第一小和第二小的基向量做贡献

也就是 1^2=3

求第5大，也就是第$101$大，需要第一小和第三小的基向量做贡献

也就是 1^4=5

注意0是否存在，当矩阵满秩时也就是全都线性无关时，不会形成0，否则会

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll n;
 5 ll p[65];
 6 
 7 void Insert(ll x)
 8 {
 9     for(int i=60;i>=0;i--)
10     {
11         if(x&(1ll<<i))
12         {
13             if(!p[i])
14             {
15                 p[i]=x;
16                 break;
17             }
18             x^=p[i];
19         }
20     }
21 }
22 ll cnt = 0;
23 ll th[65];
24 
25 void rebuild()
26 {
27     for(int i=60;i>=0;i--)
28         for(int j=i-1;j>=0;j--)
29             if(p[i]&(1ll<<j))
30                 p[i]^=p[j];
31 
32     for(int i=0;i<=60;i++)
33         if(p[i])
34             th[cnt++]=p[i];
35 }
36 
37 ll query(ll x)
38 {
39     if (x>=(1ll<<cnt))
40         return -1;
41     ll ans=0;
42     for(ll j=60;j>=0;j--)
43         if ((x&1ll<<j))
44             ans^=th[j];
45 
46     return ans;
47 }
48 
49 int main()
50 {
51     ll t,q;
52     ll x;
53     cin>>t;
54     for(int kase=1;kase<=t;kase++)
55     {
56         memset(th,0,sizeof(th));
57         memset(p,0,sizeof(p));
58         cnt=0;
59         cin>>n;
60         for(int i=1;i<=n;i++)
61         {
62             scanf("%lld",&x);
63             Insert(x);
64         }
65         rebuild();
66         cin>>q;
67         printf("Case #%d:
",kase);
68         for(int i=1;i<=q;i++)
69         {
70             scanf("%lld",&x);
71             if(cnt!=n)///注意是否取到0
72                 x--;
73             printf("%lld
", query(x));
74         }
75     }
76     return 0;
77 }

View Code

•区间线性基

•离线线性基

cf1100F(离线线性基)

按照r排序，如果base[i]存在的话,用靠后的x代替插入时求最大值

为什么用靠后的x而不是靠前的呢？因为$r$是升序排序，比起前边的更有可能要后边的

•离线代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e6+5;
 4 
 5 int a[maxn];
 6 int ans[maxn];
 7 int n,m;
 8 struct Q
 9 {
10     int l,r;
11     int index;
12 }q[maxn];
13 bool cmp(Q a,Q b)
14 {
15     return a.r<b.r;
16 }
17 
18 int base[maxn],p[maxn];
19 
20 void Insert(int pos,int x)
21 {
22     for(int i=20;i>=0;i--)
23     {
24         if(x&(1<<i))
25         {
26             if(!base[i])
27             {
28                 base[i]=x;
29                 p[i]=pos;
30                 return ;
31             }
32             else if(pos>p[i])
33             {
34                 swap(p[i],pos);
35                 swap(base[i],x);
36             }
37             x^=base[i];
38         }
39     }
40 }
41 
42 int getMax(int k)
43 {
44     int l=q[k].l,r=q[k].r;
45     int ans=0;
46 
47     for(int i=20;i>=0;i--)
48         if(p[i]>=l&&p[i]<=r)
49             ans=max(ans,ans^base[i]);
50 
51     return ans;
52 }
53 
54 void Solve()
55 {
56     sort(q+1,q+1+m,cmp);
57     int k=1;
58     for(int i=1;i<=n;i++)
59     {
60         Insert(i,a[i]);
61 
62         while(i == q[k].r)
63         {
64             ans[q[k].index]=getMax(k);
65             k++;
66         }
67     }
68 }
69 
70 int main()
71 {
72     scanf("%d",&n);
73     for(int i=1;i<=n;i++)
74         scanf("%d",a+i);
75     scanf("%d",&m);
76     for(int i=1;i<=m;i++)
77     {
78         scanf("%d%d",&q[i].l,&q[i].r);
79         q[i].index=i;
80     }
81 
82     Solve();
83     for(int i=1;i<=m;i++)
84         printf("%d
",ans[i]);
85 }

View Code

•在线线性基

在线线性基就是在离线的基础上多开一维，

使得记录插入每一个数后的base

在$[l,r]$区间内操作就只找在此范围内插入的值

重点在于复制前面的信息防止丢失，在旧信息的基础上更新信息

•在线代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5e5+50;
 4 
 5 int n,q;
 6 int a[maxn];
 7 int base[maxn][40];
 8 int p[maxn][40];
 9 
10 void Insert(int k,int x,int pos)
11 {
12     for(int i=30;i>=0;i--)
13     {
14         if(x&(1<<i))
15         {
16             if(!base[k][i])
17             {
18                 base[k][i]=x;
19                 p[k][i]=pos;
20                 return ;
21             }
22             else if(pos>p[k][i])
23             {
24                 swap(pos,p[k][i]);
25                 swap(x,base[k][i]);
26             }
27             x^=base[k][i];
28         }
29     }
30 }
31 
32 int Max(int l,int r)
33 {
34     int ans=0;
35     for(int i=30;i>=0;--i)
36         if(p[r][i]>=l)
37             ans=max(ans,ans^base[r][i]);
38     return ans;
39 }
40 void Solve()
41 {
42     for(int i=1;i<=n;++i)
43     {
44         memcpy(base[i],base[i-1],sizeof(base[i-1]));
45         memcpy(p[i],p[i-1],sizeof(p[i-1]));
46 
47         Insert(i,a[i],i);
48     }
49 
50     while(q--)
51     {
52         int l,r;
53         scanf("%d%d",&l,&r);
54 
55         printf("%d
",Max(l,r));
56     }
57 }
58 int main()
59 {
60     scanf("%d",&n);
61     for(int i=1;i <= n;++i)
62         scanf("%d",a+i);
63     scanf("%d",&q);
64 
65     Solve();
66 
67     return 0;
68 }

View Code

•线性基+线段树

•模板

  1 ///区间线性基
  2 ///线性基+线段树
  3 /*给定n和a1 a2 a3...an
  4 
  5 有q个询问：
  6 
  7 给定l,r
  8 
  9 求在al...ar中选取任意个
 10 
 11 使得他们的异或和最大
 12 */
 13 #include<bits/stdc++.h>
 14 using namespace std;
 15 #define ll long long
 16 const int maxn=5e5+5;
 17 int n,q;
 18 int a[maxn];
 19 struct Seg
 20 {
 21     int l,r;
 22     int mid(){return l+((r-l)>>1);}
 23     int p[25];
 24     void Insert(int x)
 25     {
 26         for(int i=20;i>=0;i--)
 27         {
 28             if(x&(1<<i))
 29             {
 30                 if(!p[i])
 31                 {
 32                     p[i]=x;
 33                     return ;
 34                 }
 35                 x^=p[i];
 36             }
 37         }
 38    }
 39 
 40    int Max()
 41    {
 42         int ans=0;
 43         for(int i=20;i>=0;i--)
 44             ans=max(ans,ans^p[i]);
 45 
 46         return ans;
 47    }
 48 }seg[maxn<<2];
 49 
 50 ///两组线性基互插
 51 Seg Merge(Seg a,Seg b)
 52 {
 53     Seg tmp=b;
 54     for(int i=0;i<=20;i++)
 55     {
 56         if(a.p[i])
 57             tmp.Insert(a.p[i]);
 58     }
 59     return tmp;
 60 }
 61 
 62 void buildSeg(int l,int r,int pos)
 63 {
 64     seg[pos].l=l;
 65     seg[pos].r=r;
 66 
 67     if(l==r)
 68     {
 69         seg[pos].Insert(a[l]);
 70         return ;
 71     }
 72 
 73     int mid=seg[pos].mid();
 74     buildSeg(l,mid,pos<<1);
 75     buildSeg(mid+1,r,pos<<1|1);
 76 
 77     seg[pos]=Merge(seg[pos<<1],seg[pos<<1|1]);
 78     seg[pos].l=l;
 79     seg[pos].r=r;
 80 }
 81 
 82 Seg Query(int l,int r,int pos)
 83 {
 84     if(seg[pos].l==l&&seg[pos].r==r)
 85         return seg[pos];
 86 
 87     int mid=seg[pos].mid();
 88     if(r<=mid)
 89         return Query(l,r,pos<<1);
 90     else if(l>mid)
 91         return Query(l,r,pos<<1|1);
 92     else
 93         return Merge(Query(l,mid,pos<<1),Query(mid+1,r,pos<<1|1));
 94 }
 95 
 96 
 97 int main()
 98 {
 99     scanf("%d",&n);
100     for(int i=1;i<=n;i++)
101         scanf("%d",&a[i]);
102     buildSeg(1,n,1);
103     scanf("%d",&q);
104     for(int i=1;i<=q;++i)
105     {
106         int l,r;
107         scanf("%d%d",&l,&r);
108 
109         Seg ans=Query(l,r,1);
110 
111         printf("%d
",ans.Max());
112     }
113 }

View Code

•例题

洛谷P4839 P哥的桶

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define ll long long
  4 const int maxn=5e5+5;
  5 int n,m;
  6 struct Seg
  7 {
  8     int l,r;
  9     int mid(){return (l+r)>>1;}
 10     int p[35];
 11     void Insert(int x)
 12     {
 13         for(int i=30;i>=0;i--)
 14         {
 15             if(x&(1<<i))
 16             {
 17                 if(!p[i])
 18                 {
 19                     p[i]=x;
 20                     return ;
 21                 }
 22                 x^=p[i];
 23             }
 24         }
 25    }
 26 
 27    int Max()
 28    {
 29         int ans=0;
 30         for(int i=30;i>=0;i--)
 31             ans=max(ans,ans^p[i]);
 32 
 33         return ans;
 34    }
 35 }seg[maxn<<2];
 36 
 37 Seg Merge(Seg a,Seg b)
 38 {
 39     Seg tmp=b;
 40     for(int i=0;i<=30;i++)
 41     {
 42         if(a.p[i])
 43             tmp.Insert(a.p[i]);
 44     }
 45     return tmp;
 46 }
 47 
 48 void buildSeg(int l,int r,int pos)
 49 {
 50     seg[pos].l=l;
 51     seg[pos].r=r;
 52 
 53     if(l==r)
 54         return ;
 55 
 56     int mid=seg[pos].mid();
 57     buildSeg(l,mid,pos<<1);
 58     buildSeg(mid+1,r,pos<<1|1);
 59 }
 60 
 61 void update(int pos,int x,int y)
 62 {
 63     if(seg[pos].l==seg[pos].r)
 64     {
 65         seg[pos].Insert(y);
 66         return ;
 67     }
 68     int mid=seg[pos].mid();
 69     if(x<=mid)
 70         update(pos<<1,x,y);
 71     else
 72         update(pos<<1|1,x,y);
 73     
 74     ///父节点也插入需要y
 75     seg[pos].Insert(y);
 76     
 77 ///Merge更好理解，但是会多个log
 78 //    int l=seg[pos].l,r=seg[pos].r;
 79 //    seg[pos]=Merge(seg[pos<<1],seg[pos<<1|1]);
 80 //    seg[pos].l=l;
 81 //    seg[pos].r=r;
 82 }
 83 
 84 Seg Query(int pos,int l,int r)
 85 {
 86     if(seg[pos].l==l&&seg[pos].r==r)
 87         return seg[pos];
 88 
 89     int mid=seg[pos].mid();
 90     if(r<=mid)
 91         return Query(pos<<1,l,r);
 92     else if(l>mid)
 93         return Query(pos<<1|1,l,r);
 94     else
 95         return Merge(Query(pos<<1,l,mid),Query(pos<<1|1,mid+1,r));
 96 }
 97 
 98 int main()
 99 {
100     scanf("%d%d",&n,&m);
101     buildSeg(1,m,1);
102     for(int i=1;i<=n;i++)
103     {
104         int op,x,y;
105         scanf("%d%d%d",&op,&x,&y);
106         if(op==1)
107             update(1,x,y);
108         else
109         {
110             Seg ans=Query(1,x,y);
111             printf("%d
",ans.Max());
112         }
113     }
114 }

View Code

•区间第k小

在线做法与第k小结合，

需要查询$[l,r]$区间的第k小

在线处理出所有的$base[k][i]$,

复制$base[l]$到$base[r]$的所有信息到$bbase$

$rebuild$处理$bbase$数组,处理出$bbase$的$th$数组

然后查找

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 int base[maxn][40],p[maxn][40];
 5 int bbase[40];
 6 int th[40];
 7 int a[maxn];
 8 int n,q;
 9 int cnt=0;
10 
11 void Insert(int k,int x,int pos)
12 {
13     for(int i=30;i>=0;i--)
14     {
15         if(x&(1<<i))
16         {
17             if(!base[k][i])
18             {
19                 base[k][i]=x;
20                 p[k][i]=pos;
21                 return ;
22             }
23             else if(pos>p[k][i])
24             {
25                 swap(p[k][i],pos);
26                 swap(base[k][i],x);
27             }
28             x^=base[k][i];
29         }
30     }
31 }
32 
33 void rebuild(int l,int r)
34 {
35     ///复制[l,r]信息到bbase
36     memset(bbase,0,sizeof(bbase));
37     for(int i=30;i>=0;i--)
38         if(p[r][i]>=l)
39             bbase[i]=base[r][i];
40 
41     for(int i=30;i>=0;i--)
42         for(int j=i-1;j>=0;j--)
43             if(bbase[i]&(1<<j))
44                 bbase[i]^=bbase[j];
45 
46     for(int i=0;i<=30;i++)
47         if(bbase[i])
48             th[cnt++]=bbase[i];
49 }
50 
51 int query(int l,int r,int k)
52 {
53     cnt=0;
54     rebuild(l,r);
55 
56     if(cnt!=r-l+1)
57         k--;
58     if(k>=(1ll<<cnt))
59         return -1;
60     int ans=0;
61     for(int i=30;i>=0;i--)
62     {
63         if(k&(1<<i))
64             ans^=th[i];
65     }
66     return ans;
67 }
68 
69 void Solve()
70 {
71     for(int i=1;i<=n;i++)
72     {
73         memcpy(base[i],base[i-1],sizeof(base[i-1]));
74         memcpy(p[i],p[i-1],sizeof(p[i-1]));
75 
76         Insert(i,a[i],i);
77     }
78     
79     cin>>q;
80     while(q--)
81     {
82         int l,r,k;
83         cin>>l>>r>>k;
84         cout<<query(l,r,k)<<endl;
85     }
86 }
87 
88 
89 int main()
90 {
91     cin>>n;
92     for(int i=1;i<=n;i++)
93         cin>>a[i];
94 
95     Solve();
96 }

View Code

•线性基变形

•例题

2019牛客多校第一场A (异或和为0的所有子集长度和)

具体思路

•代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define mem(a,b) memset(a,b,sizeof(a))
  4 #define ll long long
  5 const int maxn=1e5+50;
  6 const int MOD=1e9+7;
  7   
  8 int n;
  9 ll a[maxn];
 10 ll base[70];
 11 ll L[maxn][70];///L[i]:前i个数（1~i）构成的基底
 12 ll R[maxn][70];///R[i]:后n-i+1个数（i~n）构成的基底
 13 bool vis[maxn];///vis[i]:判断a[i]是否在这n个数构成的基底中
 14   
 15 bool Insert(ll x)
 16 {
 17     for(int i=60;i >= 0;--i)
 18     {
 19         if(x>>i&1)
 20         {
 21             if(!base[i])
 22             {
 23                 base[i]=x;
 24                 return true;
 25             }
 26             x ^= base[i];
 27         }
 28     }
 29     return false;
 30 }
 31 ll qPow(ll a,ll b,ll mod)
 32 {
 33     ll ans=1;
 34     a %= mod;
 35     while(b)
 36     {
 37         if(b&1)
 38             ans=ans*a%mod;
 39         a=a*a%mod;
 40         b >>= 1;
 41     }
 42     return ans;
 43 }
 44 ll Solve()
 45 {
 46     mem(base,0);
 47     for(int i=1;i <= n;++i)
 48     {
 49         vis[i]=Insert(a[i]);
 50         memcpy(L[i],base,sizeof(base));
 51     }
 52       
 53     mem(base,0);
 54     mem(R[n+1],0);
 55     for(int i=n;i >= 1;--i)
 56     {
 57         Insert(a[i]);
 58         memcpy(R[i],base,sizeof(base));
 59     }
 60   
 61     int cnt=n;
 62     for(int i=0;i <= 60;++i)
 63         if(base[i])
 64             cnt--;
 65     ///计算出不在基底中的数对答案的贡献
 66     ll ans=cnt*qPow(2,cnt-1,MOD);
 67   
 68     for(int i=1;i <= n;++i)
 69     {
 70         if(!vis[i])
 71             continue;
 72   
 73         ///base:除a[i]外的其他n-1个数构成的基底
 74         memcpy(base,L[i-1],sizeof(L[i-1]));
 75         for(int j=0;j <= 60;++j)
 76             if(R[i+1][j])
 77                 Insert(R[i+1][j]);
 78   
 79         if(Insert(a[i]))///判断a[i]是否还可插入
 80             continue;
 81   
 82         cnt=n;
 83         for(int j=0;j <= 60;++j)
 84             if(base[j])
 85                 cnt--;
 86         ///a[i]对答案的贡献
 87         ans += qPow(2,cnt-1,MOD);
 88         ans %= MOD;
 89     }
 90     return ans;
 91 }
 92 int main()
 93 {
 94     while(~scanf("%d",&n))
 95     {
 96         for(int i=1;i <= n;++i)
 97             scanf("%lld",a+i);
 98   
 99         printf("%lld
",Solve()%MOD);
100     }
101     return 0;
102 }

View Code