线性基

作者：张帅

异或（XOR）

要明白线性基，首先要知道什么是异或。

异或是一种逻辑运算，通常用符号 ^（在编程语言中）或 ⊕（数学符号）表示。遵循相同为0，不同为1的规则。即下图所示：

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

异或满足的性质：

1.交换律：A ^ B = B ^ A

2.结合律：A ^ (B ^ C) = (A ^ B) ^ C

3.自反性：A ^ A = 0，A ^ 0 = A

概念

线性基就是一个所含数字个数最小的集合，使得原先集合中的任意元素都可以用线性基中的若干元素异或和表示。

性质

线性基中任意数异或和不为0。

以任意顺序枚举集合中的元素，所得集合大小相同。

若线性基大小为s，则一共可以表示出2^s`个数；若线性基中存在二进制第i位为1的数，则该线性基共能表示出2^s-1个二进制第i位为1的数。

代码实现

void init (lol box) {
        for(int i=50;i>=0;i--) {
                if(!(box>>i&1)) continue;               //第i位为0就跳过
                if(!arr[i]) {++cnt,arr[i]=box;break;}   
                else box^=arr[i]; 
        } 
}

我们着重解释一下if(!(box>>i&1)) continue语句

高斯消元思想

线性基的构建类似于矩阵的行阶梯形：

每个基元素 arr[i] 是一个主元，控制唯一的最高位非零列。

消去其他数的该位，保证基的唯一性和极小性。

假设有三个数：

5 (101)

3 (011)

4 (100)

构建后的线性基（满足最高位独立）：

arr[2] = 101 (最高位 2)

arr[1] = 011 (最高位 1)

arr[0] = 001 (最高位 0)

每个 arr[i] 的最高位 i 都不重复。

如何维护「最高位独立」？

在插入新数 box时：

1. 从最高位向最低位遍历（for (i=50; i>=0; i--)）。

2. 如果 box 的第 i 位为 1：

   若 arr[i] 为空 ➔ 直接存入 arr[i] = box（占用该最高位）。

   若 arr[i] 非空 ➔ box ^= arr[i]（消去 box 的第 i 位，防止重复控制）。

3. 最终要么成功插入，要么 box 被消成 0（说明它可以由现有基表示）。

如果违反最高位独立：

​ 假设arr[2] = 101再直接插入110而不消去：

​ arr[2] 已经管理最高位 2，新数 110 也试图占用该位。

​ 线性相关性：5 ^ 6 = 3，说明这两个数其实是相关的（可以用更小的基表示）。

例题

P3857

#include<bits/stdc++.h>
#define lol long long
using namespace std;
const int N=51,mod=2008;
int cnt;
lol arr[N];
void init (lol box) {
    for(int i=50;i>=0;i--) {
        if(!(box>>i&1)) continue; 
        if(!arr[i]) {++cnt,arr[i]=box;break;}
        else box^=arr[i];
    }
}
int main(){
    int n,m; scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        char s[N]; scanf("%s",s);
        int len=strlen(s); lol x=0;
        for(int i=0;i<len;i++) x+=(1ll<<(n-i))*(s[i]=='O');
        init(x);
    }
    printf("%lld\n",(1ll<<cnt)%mod);
    return 0;
}