xor basis, XOR 기저, linear basis, GF(2) basis, XOR linear basis, xor-basis
정의
XOR 기저 (XOR Basis, Linear Basis over GF(2)) 는 정수 집합 S 의 XOR 합 (XOR span) 으로 만들 수 있는 모든 값을 생성하는 최소 부분집합 B. B 의 크기는 |B| ≤ log2(max(S)) 이며, 최대 XOR 부분집합 합, k-번째 XOR, 존재 여부 판정 을 O(log MAX) 에 처리.
문제 상황과 동기
N 개의 정수 (각 ≤ 10^18) 에 대해, 부분집합의 XOR 로 만들 수 있는 최댓값을 구하라.
naive (부분집합 전탐색): O(2^N). N = 10^5 면 불가능.
XOR basis: 각 수를 GF(2) 의 60차원 벡터로 보고 Gaussian elimination 으로 기저 추출. O(N log MAX).
핵심 통찰: XOR 은 GF(2) 위의 벡터 덧셈. 60비트 정수는 60차원 벡터 공간. 기저는 최대 60개.
basis[i] = i번 비트가 leading bit 인 기저 벡터insert(x): for i = LOG..0: if x 의 i번 비트가 0: continue if basis[i] == 0: basis[i] = x; return x ^= basis[i]
x 가 이미 기저 span 안에 있으면 0 이 되어 삽입되지 않음.
최대 XOR
maxXor(): res = 0 for i = LOG..0: if (res ^ basis[i]) > res: res ^= basis[i] return res
알고리즘
insert(x): for i = LOG..0: if !(x>>i & 1): continue if !basis[i]: basis[i] = x; return x ^= basis[i]maxXor(): res = 0 for i = LOG..0: res = max(res, res ^ basis[i]) return rescontains(x): for i = LOG..0: if !(x>>i & 1): continue if !basis[i]: return false x ^= basis[i] return x == 0
구현
#include <bits/stdc++.h>using namespace std;using ll = long long;struct XORBasis { static const int LOG = 60; ll basis[LOG + 1] = {}; void insert(ll x) { for (int i = LOG; i >= 0; i--) { if (!(x >> i & 1)) continue; if (!basis[i]) { basis[i] = x; return; } x ^= basis[i]; } } ll maxXor() { ll res = 0; for (int i = LOG; i >= 0; i--) if ((res ^ basis[i]) > res) res ^= basis[i]; return res; } bool contains(ll x) { for (int i = LOG; i >= 0; i--) { if (!(x >> i & 1)) continue; if (!basis[i]) return false; x ^= basis[i]; } return x == 0; }};int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; XORBasis xb; for (int i = 0; i < n; i++) { ll x; cin >> x; xb.insert(x); } cout << "max xor: " << xb.maxXor() << '';}
LOG = 60class XORBasis: def __init__(self): self.basis = [0] * (LOG + 1) def insert(self, x): for i in range(LOG, -1, -1): if not (x >> i & 1): continue if not self.basis[i]: self.basis[i] = x; return x ^= self.basis[i] def max_xor(self): res = 0 for i in range(LOG, -1, -1): if (res ^ self.basis[i]) > res: res ^= self.basis[i] return res def contains(self, x): for i in range(LOG, -1, -1): if not (x >> i & 1): continue if not self.basis[i]: return False x ^= self.basis[i] return x == 0n = int(input())xb = XORBasis()for x in map(int, input().split()): xb.insert(x)print(f"max xor: {xb.max_xor()}")
import java.util.*;import java.io.*;public class Main { static class XORBasis { static final int LOG = 60; long[] basis = new long[LOG + 1]; void insert(long x) { for (int i = LOG; i >= 0; i--) { if ((x >> i & 1) == 0) continue; if (basis[i] == 0) { basis[i] = x; return; } x ^= basis[i]; } } long maxXor() { long res = 0; for (int i = LOG; i >= 0; i--) if ((res ^ basis[i]) > res) res ^= basis[i]; return res; } boolean contains(long x) { for (int i = LOG; i >= 0; i--) { if ((x >> i & 1) == 0) continue; if (basis[i] == 0) return false; x ^= basis[i]; } return x == 0; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); XORBasis xb = new XORBasis(); StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) xb.insert(Long.parseLong(st.nextToken())); System.out.println("max xor: " + xb.maxXor()); }}
stdin
43 5 9 11
결과
max xor: 15
복잡도
항목
값
삽입 (insert)
O(log MAX) = O(60)
최대 XOR (maxXor)
O(log MAX)
존재 여부 (contains)
O(log MAX)
공간
O(log MAX) = O(60)
전체 N 개 삽입
O(N log MAX)
log MAX ≤ 60 (10^18 기준) 이므로 사실상 상수 시간.
변형
연산
설명
최소 XOR
0 이 아닌 최소값
k-번째 XOR
정규화 후 k 의 비트로 조합
XOR 차원
선형 독립 벡터 개수
XOR 합성 (merge)
두 basis 합집합
동적 basis
offline 분할 정복
함정
1. LOG 크기
long long 은 63비트까지. 보통 60 (10^18, 2^60). 문제에 따라 62까지 필요.
2. k-번째 XOR 의 k
0 번째 = 항상 0 (공집합). k 가 1-indexed 인지 확인.
3. 0 의 처리
0 은 항상 만들 수 있음. contains(0) = true. 하지만 basis 에는 들어가지 않음.
4. long long shift
1LL << i 에서 i >= 63 이면 UB. unsigned long long 또는 __int128.
💬 댓글