Subset XOR Maximization

Bard·2022년 3월 18일
2

Hard Algorithms

목록 보기
2/5
post-thumbnail

문제 설명

집합 SS = {a1,,ana_1, \cdots , a_n} (1ai10181 ≤ a_i ≤ 10^{18}, 1n100,0001 ≤ n ≤ 100,000) 이 입력으로 주어진다.

이때 집합 SS의 부분 집합(X={x1,xt}SX = \{x_1, \cdots x_t\} \subset S) 중 x1x2...xt1xtx_1 \oplus x_2 ... \oplus x_{t-1} \oplus x_t 의 최댓값을 구하는 문제이다.
(\oplus는 배타적 논리합, 즉 XOR 연산을 의미한다.)

Subset XOR Maximization

예를 들어 S={1,3,4,6,8,11}S = \{1,3,4,6,8,11\} 로 주어졌다고 가정해보자.

이 때, 주어진 수들을mod2\mod 2 로 계산된 벡터들로 볼 수 있다. (이진법이라는 얘기다.)

[0001],[0011],[0100],\begin{bmatrix}0&0&0&1\end{bmatrix}, \begin{bmatrix}0&0&1&1\end{bmatrix}, \begin{bmatrix}0&1&0&0\end{bmatrix},

[0110],[1000],[1011]\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 연산으로 말이다.

[101110000110010000110001][101101100010000100000000][100001000010000100000000]\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로 만들수 있는 최댓값을 쉽게 구할 수 있다.

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

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

[1000]=113\begin{bmatrix}1&0&0&0\end{bmatrix} = 11 \oplus 3
[0100]=631\begin{bmatrix}0&1&0&0\end{bmatrix} = 6 \oplus 3 \oplus 1
[0010]=31\begin{bmatrix}0&0&1&0\end{bmatrix} = 3 \oplus 1
[0001]=1\begin{bmatrix}0&0&0&1\end{bmatrix} = 1

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

[1111]\begin{bmatrix}1&1&1&1\end{bmatrix}
=(113)(631)(31)1= (11 \oplus 3) \oplus (6 \oplus 3 \oplus 1) \oplus (3 \oplus 1) \oplus 1
=116333111= 11 \oplus 6 \oplus 3 \oplus 3 \oplus 3 \oplus 1 \oplus 1 \oplus 1
=11631= 11 \oplus 6 \oplus 3 \oplus 1

이렇게 구한 열벡터들을 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)
            	
profile
The Wandering Caretaker

3개의 댓글

comment-user-thumbnail
2022년 3월 24일

잘 배워가요!!

1개의 답글
comment-user-thumbnail
2023년 12월 8일

xor과 관련된 문제들을 풀 때마다 몇 개의 정수들을 xor해서 그 값을 어떻게 최대화할 수 있을지 궁금했었는데, 이런 방식으로 해결할 수 있군요. xor을 Z_2에서의 n차원 벡터로 해석하는 것은 정말로 좋은 이해방법인 것 같습니다. 좋은 글 감사합니다!

답글 달기