SRM 621 Div2 L3 MixingColors：高斯消元求線性基/矩陣秩

題目大意

給定一組整數 colors，每個整數可視為二進制向量。求這些向量張成的線性空間的基的大小，即矩陣的秩。等價於求最大線性無關子集的大小。

核心算法：高斯消元（位運算版）

從最高位（第 31 位）向最低位掃描，維護一組基向量。對於每一位：

1. 尋找未使用的向量中該位為 1 的「主元」。
2. 若找到，標記為已用，基計數 +1，並將其餘該位為 1 的向量異或主元，消去該位。
3. 若未找到，繼續下一位。

最終基的個數即為答案。

C++ 代碼實現

#include <vector>
#include <cstring>
using namespace std;

class MixingColors {
public:
    int minColors(vector<int> colors) {
        int res = 0;
        int n = colors.size();
        bool used[55] = {false};

        for (int i = 31; i >= 0; i--) {
            int pivot = 0;
            for (int j = 0; j < n; j++) {
                if (used[j]) continue;
                if ((colors[j] >> i) & 1) {
                    if (!pivot) {
                        pivot = colors[j];
                        used[j] = true;
                        ++res;
                    } else {
                        colors[j] ^= pivot; // 消去第 i 位
                    }
                }
            }
        }
        return res;
    }
};

算法解析

• 時間複雜度：O(32 × n) = O(n)，n ≤ 50，極其高效。
• 空間複雜度：O(n)。
• 關鍵技巧：利用異或（^）實現 GF(2) 上的向量減法，避免浮點運算。

線性基相關知識延伸

1. 線性基：一組線性無關向量，能表示原向量組的所有線性組合（這裡是異或組合）。
2. 應用場景：最大異或子集、第 k 小異或值、子集異或和計數等。
3. 構建模板：維護 basis[32] 陣列，insert(x) 從高位到低位嘗試插入，若 basis[i] 為空則佔位，否則 x ^= basis[i]。

總結

本題是線性基/高斯消元在 GF(2) 域上應用的經典入門題。掌握「從高位到低位貪心構建基」的模板，可解決大多數異或相關的線性代數問題。代碼簡潔、無浮點誤差、複雜度低，是競賽編程中的必備技能。