Transofrmação do Problema em Sistema Linear

O problema dos interruptores pode ser modelado como um sistema de equações lineares sobre o corpo finito GF(2), onde a adição corresponde à operação XOR. Cada interruptor é representado por uma variável binária indicando se será acionado ou não.

Seja n a quantidade de interruptores. Dfeinimos variáveis y<sub>1</sub>, y<sub>2</sub>, ..., y<sub>n</sub> onde y<sub>i</sub> = 1 significa que o i-ésimo interruptor será pressionado. A mudança de estado segue a lógica: estado final = estado inicial XOR (soma dos efeitos das operações).

Para cada interruptor i, estabelecemos:

estado_inicial[i] XOR (Σ y[j] · afeta[j][i]) = estado_desejado[i]

Reorganizando, obtemos o termo independente:

Σ y[j] · afeta[j][i] = estado_inicial[i] XOR estado_desejado[i]

Estrutura da Matriz de Coeficientes

A matriz ampliada possui dimensões n × (n+1):

• Elemento M[i][j] = 1 se pressionar o interruptor j altera o estado do interruptor i
• A diagonal principal sempre contém 1 (cada interruptor afeta a si mesmo)
• A última coluna armazena estado_inicial[i] ⊕ estado_desejado[i]

Algoritmo de Eliminação em GF(2)

A eliminação gaussiana adaptada para operações XOR procede da seguinte forma:

int eliminar(vector<bitset<MAXN+1>>& mat, int linhas, int colunas) {
    int piv = 0;  // contador de pivôs encontrados
    
    for (int col = 0; col < colunas && piv < linhas; col++) {
        // busca linha com coeficiente 1 na coluna atual
        int sel = -1;
        for (int i = piv; i < linhas; i++) {
            if (mat[i][col]) {
                sel = i;
                break;
            }
        }
        
        if (sel == -1) continue;  // coluna sem pivô, próxima coluna
        
        swap(mat[sel], mat[piv]);
        
        // eliminação: zera demais entradas da coluna
        for (int i = 0; i < linhas; i++) {
            if (i != piv && mat[i][col]) {
                mat[i] ^= mat[piv];  // XOR entre linhas
            }
        }
        piv++;
    }
    
    // verifica inconsistências
    for (int i = piv; i < linhas; i++) {
        if (mat[i][colunas]) return -1;  // sistema impossível
    }
    
    return piv;  // retorna número de pivôs (posto da matriz)
}

Análise de Soluções e Variáveis Livres

Após a eliminação, o sistema pode apresentar três comportamentos distintos:

Sistema inconsistente: quando existe linha da forma [0 0 ... 0 | 1], indicando equação 0 = 1. Neste caso, não existe configuração de acionamento que satisfaça as condições.

Sistema determinado: quando o posto da matriz de coeficientes igual ao número de variáveis (posto = n). Existe solução única.

Sistema subdeterminado: quando posto < n. As n - posto variáveis não associadas a pivôs são livres, podendo assumir qualquer valor. Cada variável livre duplica o espaço de soluções, resultando em 2<sup>(n-posto)</sup> configurações válidas.

Implementação Completa

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

const int MAX = 35;

int resolver() {
    int n;
    cin >> n;
    
    vector<bitset<MAX>> eq(n);
    vector<int> ini(n), fim(n);
    
    // lê estados
    for (int i = 0; i < n; i++) cin >> ini[i];
    for (int i = 0; i < n; i++) cin >> fim[i];
    
    // inicializa matriz: diagonal e termos independentes
    for (int i = 0; i < n; i++) {
        eq[i][i] = 1;                    // auto-efeito
        eq[i][n] = ini[i] ^ fim[i];      // diferença desejada
    }
    
    // lê relacionamentos adicionais
    int m;
    cin >> m;
    for (int k = 0; k < m; k++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        eq[v][u] = 1;  // u afeta v
    }
    
    int posto = 0;
    for (int c = 0; c < n && posto < n; c++) {
        int escolhida = -1;
        for (int l = posto; l < n; l++) {
            if (eq[l][c]) { escolhida = l; break; }
        }
        if (escolhida == -1) continue;
        
        swap(eq[escolhida], eq[posto]);
        
        for (int l = 0; l < n; l++) {
            if (l != posto && eq[l][c])
                eq[l] ^= eq[posto];
        }
        posto++;
    }
    
    // detecta impossibilidade
    for (int i = posto; i < n; i++)
        if (eq[i][n]) return -1;
    
    return 1 << (n - posto);  // 2^(variáveis livres)
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int casos;
    cin >> casos;
    while (casos--) {
        int ans = resolver();
        if (ans == -1) cout << "Oh,it's impossible~!!\n";
        else cout << ans << '\n';
    }
    return 0;
}

Otimizações e Considerações

O uso de bitset proporciona paralelismo em nível de bits, reduzindo a complexidade de cada operação de linha de O(n) para O(n/64) ou O(n/32) dependendo da arquitetura. Para n ≤ 30, a matriz inteira cabe em poucos registradores, tornando a solução extremamente eficiente.

A escolha da forma reduzida de escada (reduced row echelon form), onde cada pivô é o único elemento não-nulo em sua coluna, simplifica a identificação de variáveis livres e permite verificação direta de consistência.