Subset XOR Maximization

문제 설명

집합 $S$ = {$a_1, \cdots , a_n$

이때 집합 $S$의 부분 집합($X = \{x_1, \cdots x_t\} \subset S$

Subset XOR Maximization

예를 들어 $S = \{1,3,4,6,8,11\}$

이 때, 주어진 수들을$\mod 2$

$\begin{bmatrix}0&0&0&1\end{bmatrix}, \begin{bmatrix}0&0&1&1\end{bmatrix}, \begin{bmatrix}0&1&0&0\end{bmatrix},$

$\begin{bmatrix}0&1&1&0\end{bmatrix}, \begin{bmatrix}1&0&0&0\end{bmatrix}, \begin{bmatrix}1&0&1& 1\end{bmatrix}$

이렇게 말이다.

선형대수학에선, RREF (Reduced Row Echelon Form) 을 이용해서 종속성을 검사하는데,
여기에서도 똑같이 할 수 있다.

주어진 수들로 RREF를 만들어보자. 단, 벡터간의 합이 아닌 XOR 연산으로 말이다.

$\begin{bmatrix}1&0&1&1\\1&0&0&0\\0&1&1&0\\0&1&0&0\\0&0&1&1\\0&0&0&1\end{bmatrix}\rArr\begin{bmatrix}1&0&1&1\\0&1&1&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\\0&0&0&0\end{bmatrix}\rArr\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\\0&0&0&0\end{bmatrix}$

이제 영벡터가 아닌 행벡터들의 Leading 1 들을 살펴보면 XOR로 만들수 있는 최댓값을 쉽게 구할 수 있다.

이해를 돕기 위해 좀 더 자세히 설명해보자.

영벡터가 아닌 행벡터들은 다음과 같이 표기된다.

$\begin{bmatrix}1&0&0&0\end{bmatrix} = 11 \oplus 3$

이 친구들을 모두 XOR 해주게 되면 다음과 같은 결과를 얻을 수 있다.

$\begin{bmatrix}1&1&1&1\end{bmatrix}$

이렇게 구한 열벡터들을 XOR basis라고 한다. XOR basis를 구한 뒤, 그때부터는 그냥 Greedy하게 선택하기만 해도 쉽게 Subset XOR Maximization을 수행할 수 있다.

예제코드

c++

#include <bits/stdc++.h>

using namespace std;
using lint = long long int;

int N;
lint basis[61];

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    lint t;
    cin >> t;
    for (int j = 60; j >= 0; j--) {
      if ((t >> j) & 1) {
        if (!basis[j]) {
          basis[j] = t;
          break;
        } else {
          t ^= basis[j];
        }
      }
    }
  }
  lint maxSum = 0;
  for (int i = 60; i >= 0; i--) {
    if (basis[i]) {
      maxSum = max({
        maxSum,
        maxSum ^ basis[i]
      });
    }
  }
  cout << maxSum;
}

python3

N = int(input())
a = list(map(int, input().split()))
basis = [0] * 61

for i in range(N):
    for j in range(60, -1, -1):
        if a[i] >> j & 1:
            if basis[j] == 0:
                basis[j] = a[i]
                break
            else:
                a[i] ^= basis[j]

maxSum = 0
for i in range(60, -1, -1):
    if basis[i]:
        maxSum = max(maxSum, maxSum ^ basis[i])

print(maxSum)