太久没怎么写线性基了，最近多校特别多线性基的题，所以写篇博客权当复习。
内容主要参考Menci关于线性基博客，menci tql
线性基是用于解决子集异或一类题目的算法。
一些定义
线性基的基本性质
线性基的构造方法
不妨设集合S中最大的数的二进制表示有L位，用一个数组a[0..L]来存储线性基。这种线性基的构造方法保证了一个特殊性质，对于每一个i，ai有以下两种可能：
我们称第i位存在于线性基中，当且仅当ai≠0。
线性基是动态构造的，只需从空的a开始，每次考虑在一个已存在的线性基中插入一个数t即可。
从t最高位上的1开始考虑，设这是第i位。如果这一位已经存在于线性基中，则我们需要将t中的这一位消掉才可以继续插入(因为只有ai的第i位可以为1)。如果这意味不存在于线性基中，则可以将t插入到ai的位置上，但插入时需要保证：
插入过程
逆序枚举t的所有为1的二进制位i，对于每个i：
线性基的合并
两个集合的线性基可以在O(log2t)的时间内进行合并，合并后得到的线性基为两个集合的并的线性基。合并时只需将一个线性基中的所有元素插入到另一个线性基中即可。
线性基的应用
最基本的应用就是解决子集最大异或和问题。
问题：给定一个集合S，求其一子集T，使得T异或和最大，求该异或和。
solution：首先求出S的线性基B，问题转化为选择B的一个子集。从高到低考虑在线性基中的二进制位i，若第i位存在于线性基中，则考虑到线性基中只有唯一一个元素的第i位为1，所以之前加入到T中的元素的异或和的第i位一定为0，故把这个元素加入到T中一定会使得答案更大。故求出线性基中所有元素的异或和，即为答案。
模板：
一、不显式构造出集合B，支持动态插入。
1 struct LinearBasis 2 { 3 long long a[MAXL + 1]; 4 5 LinearBasis() 6 { 7 std::fill(a, a + MAXL + 1, 0); 8 } 9 10 LinearBasis(long long *x, int n) 11 { 12 build(x, n); 13 } 14 15 void insert(long long t) 16 { 17 for (int j = MAXL; j >= 0; j--) 18 { 19 if (!t) return; 20 if (!(t & (1ll << j))) continue; 21 22 if (a[j]) t ^= a[j]; 23 else 24 { 25 for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k]; 26 for (int k = j + 1; k <= MAXL; k++) if (a[k] & (1ll << j)) a[k] ^= t; 27 a[j] = t; 28 break; 29 } 30 } 31 } 32 33 // 数组 x 表示集合 S，下标范围 [1...n] 34 void build(long long *x, int n) 35 { 36 std::fill(a, a + MAXL + 1, 0); 37 38 for (int i = 1; i <= n; i++) 39 { 40 insert(x[i]); 41 } 42 } 43 44 long long queryMax() 45 { 46 long long res = 0; 47 for (int i = 0; i <= MAXL; i++) res ^= a[i]; 48 return res; 49 } 50 51 void mergeFrom(const LinearBasis &other) 52 { 53 for (int i = 0; i <= MAXL; i++) insert(other.a[i]); 54 } 55 56 static LinearBasis merge(const LinearBasis &a, const LinearBasis &b) 57 { 58 LinearBasis res = a; 59 for (int i = 0; i <= MAXL; i++) res.insert(b.a[i]); 60 return res; 61 } 62 };
二、显式构造出集合B，不支持动态插入。
1 struct LinearBasis 2 { 3 std::vector<long long> v; 4 int n; // 原有集合 S 的大小 5 6 // 数组 x 表示集合 S，下标范围 [1...n] 7 void build(long long *x, int n) 8 { 9 this->n = n; 10 std::vector<long long> a(MAXL + 1); 11 12 for (int i = 1; i <= n; i++) 13 { 14 long long t = x[i]; 15 16 for (int j = MAXL; j >= 0; j--) 17 { 18 if ((t & (1ll << j)) == 0) continue; 19 20 if (a[j]) t ^= a[j]; 21 else 22 { 23 for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k]; 24 for (int k = j + 1; k <= MAXL; k++) if (a[k] & (1ll << j)) a[k] ^= t; 25 26 a[j] = t; 27 break; 28 } 29 } 30 } 31 32 v.clear(); 33 for (int i = 0; i <= MAXL; i++) if (a[i]) v.push_back(a[i]); 34 } 35 36 long long queryMax() 37 { 38 long long x = 0; 39 for (size_t i = 0; i < v.size(); i++) x ^= v[i]; 40 return x; 41 } 42 };
相关题目
原文：https://www.cnblogs.com/JHSeng/p/11267050.html
