前言

线性基是向量空间的一组基，通常可以解决有关异或的一些题目。──OI Wiki

  • 另外，为了描述方便，我们不严谨的约定下文中出现的所有“子集”都非空

    线性基的作用

  • 求解一个数集中 集合内异或和最大/最小的子集中元素的异或和（即从集合中挑选任意多个数，求异或和的最值）

  • 在线性基的帮助下，一个无序的异或和问题可以转化为贪心问题

线性基的性质

虽然我不知道为什么所有有关线性基的文章里都会把这个放在前面，但是我还是放一下吧

  • ① 线性基所有子集的异或和形成的集合 与 原数集所有子集的异或和形成的集合 相同
    • (线性基内所有的元素都是通过原数集中的元素做异或运算得到的)
  • ② 线性基是满足①性质的最小集合
  • ③ 线性基不存在异或和为[算法] 线性基 - 图1的子集
    • (线性基所有元素的得到不存在与[算法] 线性基 - 图2异或的过程)
  • ④ 线性基所有子集的异或和形成的集合为无重集合
    • (本质上和性质③一样)
  • ⑤ 线性基内元素二进制下最高位都在不同的位置
    • (因为线性基的实现就是以最高位位置为索引存的一维数组)

线性基的构造

似乎所有题解都是在摆出一大堆说明后直接开始讲怎么构造(虽然似乎这样更有效率)，但是我其实一开始看得一头雾水也挺悲(虽然其实真的直接看会快很多)，但我还是决定把分析推导过程谈一谈(当然只是我自己的)。

考虑异或和最大问题

首先有关异或这个运算的特性，不再详细说明，提出关键词：可逆

想让一个数最大，在二进制下我们肯定希望它的最高位的位置能更大，一个最高位在第8位的肯定比最高位在第4位的大。

然后，比如说我们现在已经有一个二进制数[算法] 线性基 - 图3_2#card=math&code=%2810100%29_2&id=iR84S)，我们想让他更大，可以让它与[算法] 线性基 - 图4_2#card=math&code=%281xxxxx%29_2&id=eAafe)异或，不管怎么样它都能变大。所以我们考虑能不能维护一个数组，下标是最高位在第[算法] 线性基 - 图5位的数。

考虑一个最高位位置各不相同的集合，可以直接按照位置从高到低贪心求解。

然而实际问题里最高位位置不一定都不同。所以我们的线性基不能直接简单存储。我们现在考虑最高位在同一个位置的两个数怎么处理。

比如有：[算法] 线性基 - 图6_2#card=math&code=x%3D%281010%29_2&id=sRf6p)，[算法] 线性基 - 图7_2#card=math&code=y%3D%281001%29_2&id=syyTs)，它们的最高位都是第四位。考虑处理顺序，我们先将[算法] 线性基 - 图8塞入了[算法] 线性基 - 图9（因为第四位实际上是用(1<<3)获得的，所以我们用[算法] 线性基 - 图10表示第[算法] 线性基 - 图11位），然后发现[算法] 线性基 - 图12的最高位也是4。如果这两个数都选择的话，就会导致第四位的[算法] 线性基 - 图13消失，所以我们考虑把[算法] 线性基 - 图14，虽然[算法] 线性基 - 图15存的是[算法] 线性基 - 图16，但是除了第四位的信息，都可以由新的[算法] 线性基 - 图17和[算法] 线性基 - 图18得到，这时候我们把[算法] 线性基 - 图19再塞入线性基就可以了。如果遇到冲突处理类似。

当我们在贪心处理的时候，如果[算法] 线性基 - 图20本来就比[算法] 线性基 - 图21大，那我们直接就不用[算法] 线性基 - 图22了。如果[算法] 线性基 - 图23比[算法] 线性基 - 图24大，那我们可以用[算法] 线性基 - 图25来表示原来的[算法] 线性基 - 图26。

简单且不严谨的归纳一下，由于异或运算的可逆性，存[算法] 线性基 - 图27和存[算法] 线性基 - 图28是一样的，但是可以造成其中一个数最高位的变化。

简单的理解是，线性基维护的是能够对第[算法] 线性基 - 图29位产生贡献的元素中的其中一个，并通过之后的部分元素与第[算法] 线性基 - 图30位元素共同维护原集合中最高位在[算法] 线性基 - 图31的元素。

线性基的实现

对于一个数[算法] 线性基 - 图32：

  • 找到它最高位的位置[算法] 线性基 - 图33（满足[算法] 线性基 - 图34%3D1#card=math&code=x%20%5C%26%20%281%3C%3Cp%29%3D1&id=ud5pq)的最大的[算法] 线性基 - 图35）
  • 检查b[p]是否为空
    • 如果为空：令b[p]为[算法] 线性基 - 图36
    • 如果非空：令[算法] 线性基 - 图37为[算法] 线性基 - 图38，重复跳回最初

最终得到线性基数组b[n]

  1. //find函数返回p
  2. rep(i,1,n){
  3.         while(1){
  4.             int p = find(a[i]);
  5.             if(!b[p]){
  6.                 b[p] = a[i];
  7.                 break;
  8.             } else {
  9.                 if(p == 0) break;
  10.                 a[i] ^= b[p];
  11.             }
  12.         } 
  13.     }

线性基的应用

求异或和最小

直接返回b[n]中的最小元素（即从小往大遍历第一个非[算法] 线性基 - 图39元素）

求异或和最大

从大往小贪心，如果b[i]能使[算法] 线性基 - 图40变大，那就异或b[i]，反之不异或。

相关题目

P3812 【模板】线性基

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i) 
  14. #define mkp std::make_pair
  15. typedef long long ll;
  16. typedef unsigned long long ull;
  17. using std::string;using std::cin;using std::cout;
  18. inline bool cmp(int x,int y){return x < y;}
  20. const int N = 1e6+9;
  21. const int inf = 1e9+9;
  22. const double eps = 1e-7;
  23. int _,n,m;
  24. ll a[2*N],b[110];
  26. inline int find(ll x){
  27.     int p = 55;
  28.     while((1ll<<p) > x && p >= 0) --p;
  29.     while((1ll<<p) & x == 0 && p >= 0) --p;
  30.     return p;
  31. }
  33. int main(){
  34.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  35.     //freopen("in.in", "r", stdin);
  36.     cin >> n;
  37.     rep(i,1,n) cin >> a[i];
  38.     rep(i,1,n){
  39.         while(1){
  40.             int p = find(a[i]);
  41.             if(!b[p]){
  42.                 b[p] = a[i];
  43.                 break;
  44.             } else {
  45.                 if(p == 0) break;
  46.                 a[i] ^= b[p];
  47.             }
  48.         } 
  49.     }
  50.     ll ans = 0;
  51.     per(i,55,0)  ans = ans > (ans ^ b[i]) ? ans : (ans ^ b[i]);
  52.     cout << ans << "\n";
  53.     return 0;
  54. }

P3857 [TJOI2008]彩灯

这道题也是一道板子题。我们先二进制状压一下每个开关的效果，然后求这些数的线性基。由于线性基的性质，所以可以得到答案就是[算法] 线性基 - 图41，其中[算法] 线性基 - 图42表示线性基中的元素个数。

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i) 
  14. #define mkp std::make_pair
  15. typedef long long ll;
  16. typedef unsigned long long ull;
  17. using std::string;using std::cin;using std::cout;
  18. inline bool cmp(int x,int y){return x < y;}
  20. const int N = 1e6+9;
  21. const int inf = 1e9+9;
  22. const double eps = 1e-7;
  23. int _,n,m;
  24. ll a[2*N],b[2*N],ans;
  25. char ch[100];
  27. inline int find(ll x){
  28.     int p = 55;
  29.     while(!(x & (1ll<<p)) && p >= 1) --p;
  30.     return p;
  31. }  
  33. int main(){
  34.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  35.     #ifdef LOCAL //use "g++ xxx.cpp -DLOCAL"
  36.         freopen("in.in", "r", stdin);
  37.     #endif
  38.     cin >> n >> m;
  39.     rep(i,1,m){
  40.         cin >> ch+1;
  41.         rep(j,1,n) a[i] = (a[i] << 1) + (ch[j] == 'O');
  42.     }
  43.     rep(i,1,m){
  44.         int p;
  45.         while(1){
  46.             p = find(a[i]);
  47.             if(!b[p]){
  48.                 b[p] = a[i];
  49.                 break;
  50.             } else {
  51.                 a[i] ^= b[p];
  52.                 if(p == 0) break;
  53.                 continue;
  54.             }
  55.         }
  56.     }
  57.     ans = 1;
  58.     per(i,55,0) if(b[i]){ans <<= 1 , ans %= 2008;}
  59.     if(ans == 1) ans = 0;
  60.     cout << ans%2008 << "\n";
  61.     return 0;
  62. }