Concepto

Una base lineal es un conjunto de vectores que forman una base en un espacio vectorial, comúnmente uitlizada para resolver problemas relacionados con operaciones XOR. — OI Wiki

En esencia, la base lineal es un conjunto derivado del original mediante un proceso basado en bits binarios. A continuación se detalla su funcionamiento.

Propiedades

1. La base lineal posee las propiedades de determinación, no redundancia y falta de orden inherentes a un conjunto.
2. Cada elemento en la base lineal tiene un bit más significativo único en su representación binaria.
3. No existe un subconjunto dentro de la base lineal cuya suma XOR sea cero.
4. El rango de valores obtenidos al XOR de cualquier subconjunto de la base lineal es idéntico al del conjunto original.
5. La base lineal minimiza el número de elementos manteniendo la propiedad anterior.
6. Los valores generados por XOR de elementos distintos en la base lineal son todos diferentes.

Construcción

El problema más frecuente es encontrar el valor máximo de la suma XOR de elementos de un conjunto. Se aborda con un enfoque codicioso.

El XOR tiene la propiedad de que si dos números difieren en un bit, ese bit se establece en 1; de lo contrario, es 0. Además, el XOR es conmutativo, por lo que el orden no afecta el resultado.

Para maximizar el valor final, se busca tener tantos bits en 1 como sea posible. La clave es procesar los números desde el bit más alto hacia abajo, ya que los bits superiores dteerminan la magnitud del valor.

Al insertar un número x con bit más alto d:

• Si la posición d está vacía, se inserta x.
• Si ya hay un valor y, se realiza x = x XOR y y se continúa hacia bits inferiores hasta que se inserte o se anule.

Este proceso garantiza que cada bit posicional tenga la oportunidad de ser 1, sin afectar el resultado final.

void agregar_a_base(long long valor) {
    int bit_max = 60; // Ajustar según rango de datos
    for (int bit = bit_max; bit >= 0; bit--) {
        if ((valor & (1LL << bit)) == 0) continue;
        if (base[bit] == 0) {
            base[bit] = valor;
            return;
        }
        valor ^= base[bit];
    }
}

La base lineal admite diversas operaciones, pero aquí se enfocan en las esenciales.

Ejemplo: [BJWC2011] Elementos

Dados n elementos, cada uno con propiedades a_i y b_i, seleccionar un subconjunto donde el XOR de todos los a_i no sea cero y maximizar la suma de los b_i. Restricciones: 1 ≤ n ≤ 1000, 1 ≤ a_i ≤ 10^18, 1 ≤ b_i ≤ 10^4.

Para garantizar que el XOR no sea cero, se asegura que los a_i tengan bits únicos mediante la base lineal. Para maximizar la suma de b_i, se ordenan los elementos por b_i de forma descendente y se insertan primero los de mayor valor.

struct Elemento {
    long long valor_a;
    int valor_b;
};

bool comparar(Elemento x, Elemento y) {
    return x.valor_b > y.valor_b;
}

bool insertar_en_base(long long k) {
    int bit_max = 60;
    for (int bit = bit_max; bit >= 0; bit--) {
        if ((k & (1LL << bit)) == 0) continue;
        if (base[bit] == 0) {
            base[bit] = k;
            return true;
        }
        k ^= base[bit];
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    vector<elemento> elems(n);
    for (int i = 0; i < n; i++) cin >> elems[i].valor_a >> elems[i].valor_b;
    sort(elems.begin(), elems.end(), comparar);
    long long suma_total = 0;
    for (auto e : elems) {
        if (insertar_en_base(e.valor_a)) suma_total += e.valor_b;
    }
    cout << suma_total << endl;
    return 0;
}
</elemento>

Ejemplo: [TJOI2008] Luces Decorativas

Hay n luces y m interruptores. Cada interruptor controla un subconjunto de luces. Determinar el número máximo de configuraciones posibles (cada luz encendida o apagada). Restricciones: 1 ≤ n, m ≤ 50.

Se modela cada interruptor como un número binario donde cada bit representa una luz (1 si la controla). Al insertar estos números en una base lineal, se obtiene una representación mínima de combinaciones XOR. Si la base tiene k elementos, hay 2^k configuraciones distintas.

int contador_base = 0;
long long base[60] = {0};

void insertar_configuracion(long long k) {
    int bit_max = 50;
    for (int bit = bit_max; bit >= 0; bit--) {
        if ((k >> bit & 1) == 0) continue;
        if (base[bit] == 0) {
            base[bit] = k;
            contador_base++;
            return;
        }
        k ^= base[bit];
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    string linea;
    for (int i = 0; i < m; i++) {
        cin >> linea;
        long long mascara = 0;
        for (int j = 0; j < linea.length(); j++) {
            if (linea[j] == 'O') mascara |= (1LL << (n - j - 1));
        }
        insertar_configuracion(mascara);
    }
    cout << (1LL << contador_base) << endl;
    return 0;
}

Ejemplo: [WC2011] Camino con Máxima Suma XOR

Dado un grafo no dirigido con n vértices y m aristas ponderadas, encontrar el camino desde el vértice 1 al n que maximice la suma XOR de los pesos de las aristas. Se pueden repetir vértices y aristas; las aristas repetidas se contabilizan múltiples veces en el XOR. Restricciones: 1 ≤ n ≤ 50000, 1 ≤ m ≤ 100000, pesos hasta 10^18.

Cualquier camino puede descomponerse en un camino simple más ciclos repetidos. La suma XOR del camino completo es la del camino simple XOR con la suma de los ciclos. Por lo tanto, se calcula la suma XOR de un camino simple desde 1 a n, se insertan las sumas XOR de todos los ciclos en una base lineal, y se busca el máximo XOR combinando el camino simple con la base.

vector<pair long="">> grafo[50005];
long long distancia[50005];
bool visitado[50005];
long long base[60] = {0};

void agregar_a_base(long long valor) {
    int bit_max = 60;
    for (int bit = bit_max; bit >= 0; bit--) {
        if ((valor & (1LL << bit)) == 0) continue;
        if (base[bit] == 0) {
            base[bit] = valor;
            return;
        }
        valor ^= base[bit];
    }
}

void dfs(int nodo, long long xor_actual) {
    visitado[nodo] = true;
    distancia[nodo] = xor_actual;
    for (auto arista : grafo[nodo]) {
        int vecino = arista.first;
        long long peso = arista.second;
        if (!visitado[vecino]) {
            dfs(vecino, xor_actual ^ peso);
        } else {
            // Insertar ciclo detectado
            agregar_a_base(distancia[nodo] ^ distancia[vecino] ^ peso);
        }
    }
}

long long consultar_maximo(long long valor_inicial) {
    long long resultado = valor_inicial;
    for (int bit = 60; bit >= 0; bit--) {
        if (base[bit] && (resultado ^ base[bit]) > resultado) {
            resultado ^= base[bit];
        }
    }
    return resultado;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        grafo[u].push_back({v, w});
        grafo[v].push_back({u, w});
    }
    dfs(1, 0);
    cout << consultar_maximo(distancia[n]) << endl;
    return 0;
}
</pair>