北京 2011 元素問題：線性基與高斯消元的貪心構造最大異或和

問題轉化

給定 n 個數對，每對含值 a 和權 x。選擇若干數使其異或和不為 0，最大化權值和。等價於：構造線性基，貪心選擇高權值向量。

線性基核心性質

• 維護一組線性無關向量，能表示原集合所有異或組合
• 每個位置至多一個向量，最高位各不相同
• 插入時從高位向低位消元

貪心策略證明思路

按權值從大到小排序，依次嘗試插入線性基。若能插入（與現有基向量無衝突），則選取該元素。正確性可用拟阵理論證明：獨立系統滿足交換性質，貪心最優。

關鍵代碼

struct Node { ll val; int w; } a[N];
bool cmp(Node a, Node b) { return a.w > b.w; }

ll basis[66], ans;
for (int i = 1; i <= n; ++i) {
    ll x = a[i].val;
    for (int k = 60; k >= 0; --k) {
        if ((x >> k) & 1) {
            if (!basis[k]) { basis[k] = x; break; }
            x ^= basis[k];
        }
    }
    if (x) ans += a[i].w;  // 成功插入，累加權值
}

複雜度分析

排序 O(n log n)，插入每數 O(log MAXA)，總體 O(n log n + n log MAXA)，n ≤ 1000 極快。

關鍵細節

1. 權值排序必須降序
2. 基數組大小覆蓋 60 位（10¹⁸ < 2⁶⁰）
3. 插入時從高位向低位消元保證基性質