線性基總結模闆

線性基

看了好多部落格，，，，

線性基是一組數，是一個集合的産物，一般用來求原集合子集異或和極值的問題。

有什麼作用？

通過線性基中元素xor出的數的值域與原來的數xor出數的值域相同。

但同時它這組數的大小隻有原集合最大數的二進制位那麽多 (60 多位)，

線性基與原集合關于異或作用一樣，但是他是最簡的，好像線性代數裡面叫做 基。

構造

求線性基時将一個數的二進制位看成一個向量。假定原集合為

數組，線性基為

對于每個

，按二進制從高位到低位掃，找最高位的 1，假如

的第

位是最高位的 1。

為 0 的話，即不存在，直接插入

；否則将

^=

，繼續掃

其實相當于不斷的将

const int base = 60;    // 一般long long 也就18位，即 60 多位二進制
int a[N], p[base+3];

for(int i = 0; i < n; i++){              // 對于每個數 a[i]
    for (int j = base; j >= 0; j--){     // 從高位到低位找 a[i] 最高位 1 的位置
        if(a[i] >> j & 1)             // 跳過前導 0
            if(!p[j]){                  // 該行沒數，直接填
                p[j] = a[i];
                break;                  // 填完跳出
            }else{
                a[i] ^= p[j];           // 該行有數，異或之後繼續看 a[i] 低位
            }
    }
}      

性質

1. 線性基中的每個向量的二進制最高位均不同，并且，我們稱二進制最高位為第 i 位的元素稱為“線性基的第 i 位”。
2. 原集合
3. 所線上性空間中每個元素都有唯一的方案由線性基中元素異或得到。

這樣我們得到的

數組是一個上三角矩陣，而且元素全都是 0， 1。

類似于這樣：

10010

01001

00100

00000

00001

可以知道線性基有多少組非零向量。

進一步簡化

數組可以得到很多資訊。下面兩種方式将

for(int i = 0; i < n; i++){          // 對于每個數 a[i]
     for (int j = base; j >= 0; j--){ // 從高位到低位找 a[i] 的第一個不為 0 的數的位置
         if(a[i] >> j == 0)
             continue;               // 跳過前導 0
         if(!p[j]){                  // 該行沒數，直接填
             p[j] = a[i];
             for (int k = j - 1; k >= 0; k--)    // 使第 p[j] 隻有第 j 位為 1
                 if(p[k] && p[j]>>k&1)
                     p[j] ^= p[k];   // 下面的行消自己
             for (int k = j + 1; k <= base; k++)
                 if(p[k] >> j&1)
                     p[k] ^= p[j];   // 自己消上面的行
             break;
         }else{
             a[i] ^= p[j];           // 該行有數
         }
     }
 }      

for(int i = base; i >= 0; i--){
     if(!p[i])
         continue;
     for (int j = i + 1; j < base; j++){
         if(p[j]>>i&1)
             p[j] ^= p[i];
     }
 }      

得到對角矩陣之後可以算第

// 求線性基時加上
for (int i = 0; i <= base; i++){    // 後面查詢用到，存非零位
    if(p[i]){
        v.push_back(p[i]);
    }
}

ll ask(ll x){               // 查詢第 k 小
    if(v.size() != n)       // 線性有關，可以異或出來 0
        x--;
    if(!x)
        return 0;           // 第一小的數是 0
    if(x >= (1LL << v.size()))  // x 超出所有能得到的值數量的範圍
        return -1;
    // 能得到 0，x 已經 -1了，x 最多達到2^v.size()-1;
    // 不等得到 0，x 最多達到v.size()-1
    ll ans = 0;
    for(int i = 0; i <= base; i++){ // 将第 i 為異或起來
        if(x >> i&1){           // 第 i 位為 1
            ans ^= v[i];
        }
    }
    return ans;
}      

參考

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