SGU 275：To xor or not to xor - 高斯消元求最大異或值

問題描述

給定 n 個整數 a_1..a_n，從中選擇若干個（可重複選？不，每個最多一次）進行異或運算，求最大可能結果。

核心思想：線性基 / 高斯消元 (GF(2))

將每個數視為 GF(2) 向量（二進制位）。目標是找到一組線性無關向量的基，使得它們的線性組合（異或）能生成最大值。貪心策略：從高位到低位，若當前位能通過現有基向量組合得到 1，則保留該基向量並消去低位。

算法步驟

1. 構建增廣矩陣：每行對應一個數的二進制位（低位在前），共 max_bit 行，n 列，最後一列為 1（表示目標向量全 1）。
2. 高斯消元：對每一行（位），尋找未被使用的列（變元）作為主元。若找到，標記該列已用，並用此行消去其他行的該列。若未找到，檢查常數項：若為 0 則該位可為 1（自由變元取 1），否則為 0。
3. 從高位到低位處理，構造出最大異或值。

代碼實現

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int mat[100][110]; // 行: 位(0..max_bit-1), 列: 變元(0..n-1) + 常數項
int vis[110];
LL a[100];

LL gauss(int equ, int var) {
    LL ans = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = equ - 1; i >= 0; --i) { // 從高位到低位
        ans <<= 1;
        int pivot = -1;
        for (int j = 0; j < var; ++j) {
            if (mat[i][j] && !vis[j]) { pivot = j; break; }
        }
        if (pivot == -1) {
            if (mat[i][var] == 0) ans |= 1; // 自由變元，可取 1
        } else {
            vis[pivot] = 1;
            ans |= 1; // 該位確定為 1
            // 消去低位行的該列
            for (int k = i - 1; k >= 0; --k) {
                if (mat[k][pivot]) {
                    for (int h = 0; h <= var; ++h)
                        mat[k][h] ^= mat[i][h];
                }
            }
        }
    }
    return ans;
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
    memset(mat, 0, sizeof(mat));
    int equ = 0;
    for (int i = 0; i < n; ++i) {
        LL x = a[i];
        int row = 0;
        while (x) {
            mat[row++][i] = x & 1;
            x >>= 1;
        }
        equ = max(equ, row);
    }
    for (int i = 0; i < equ; ++i) mat[i][n] = 1; // 目標全 1
    printf("%lld\n", gauss(equ, n));
    return 0;
}

關鍵點

• 矩陣行數 = 最大位數 (≤ 60)，列數 = n + 1。
• 高斯消元在 GF(2) 上進行，加法 = 異或 (^)。
• 從高位向低位消元，貪心構造最大值。
• 常數項全 1 表示希望每位最終為 1。

總結

求子集異或最大值等價於線性基構造，高斯消元是通用方法。本題將目標設為全 1，通過消元判斷每位能否為 1，從而構造最大值。