주어진 수들의 XOR 연산으로 만들 수 있는 수
주어진 수들의 XOR 연산으로 만들 수 있는 수
자연수의 집합 ${a_1, a_2, …, a_N}$ 이 주어집니다.
우리는 이 중 두 개의 원소를 골라 XOR한 결과를 집합에 추가할 수 있습니다.
이 때, 다음 문제들에 대해 생각해보겠습니다.
- 자연수 $b$가 주어질 때, 이 $b$가 집합의 원소가 될 수 있는지 판별하기.
- 이 집합에 들어갈 수 있는 원소의 최대 개수 구하기.
이 두 문제에 빠르게 답할 수 있는 방법을 알아보겠습니다.
우선, 첫번째로 어떤 수들이 집합에 추가 될 수 있는지 알아보겠습니다.
규칙에 의해 다음과 같은 꼴의 수들이 집합에 추가될 수 있습니다.
$(((a_{i_1} XOR$ $a_{i_2}) XOR$ $a_{i_3}) XOR$ $a_{i_4})$ $… XOR$ $a_{i_k}$
한편, XOR은 결합 법칙이 성립하므로 이는
$a_{i_1} XOR$ $a_{i_2} XOR$ $a_{i_3} XOR$ $a_{i_4} XOR$ $…XOR$ $a_{i_k}$
와 같이 나타낼 수 있습니다.
이제 이 식을 선형 대수학적으로 생각해 봅시다.
어떤 자연수의 이진법 표현을 GF(2) 상에서의 벡터로 해석할 수 있습니다.
예를 들어, $13 = 1101_{(2)}$ 를 [1 0 1 1]$^T$ 로 해석하는 것입니다.
그러면 XOR은 이 벡터들 사이에 더하기 연산과 같고, 위에서 구한 식은 GF(2) 상의 벡터들의 선형 결합으로 해석할 수 있습니다.
즉, 이 집합에 포함될 수 있는 벡터는 주어진 벡터들이 span하는 공간에 포함된 모든 벡터들일 것입니다.
따라서 위의 문제들은 아래와 같은 물음으로 바뀝니다.
- 벡터 b가 주어지면, 이 벡터가 문제에서 주어진 벡터들이 span하는 공간 위에 있는지 판별하기
- 문제에서 주어진 벡터들이 span하는 공간의 basis의 부분집합의 개수 구하기
문제에서 주어진 벡터들이 span 하는 공간에 대한 정보를 가장 직접적이고 간결하게 얻을 수 있는 것이 그 공간의 basis이기 때문에 basis를 구해보도록 합시다.
주어진 벡터들의 basis를 구하는 간단한 방법은 각 벡터를 row로 가지는 matrix의 row echelon form을 구하는 것입니다. 여기서 0 vector가 아닌 row vector들이 basis가 되는 것이죠.
이 때 드는 시간은 $O(Nlog^2MAXVAL)$ 입니다.
$a_i$ 의 크기가 $10^9$정도라고 해도 $logMAXVAL$이 30 정도로 작기 때문에 꽤나 효율적입니다.
이렇게 row echelon form을 통해 basis를 구했다면, 위의 문제들을 간단하게 해결할 수 있습니다.
| 먼저, 2번은 간단합니다. 답은 $2^{ | basis | }$ 가 될 것입니다. |
| 이 값은 $O(log | basis | )$ 시간에 구할 수 있습니다. |
또한 1번의 답도 간단하게 구할 수 있습니다.
basis들을 row로 가지는 행렬을 $A$라고 하면, $Ax=b$의 해가 존재하는지 판별하는 것이고 이는 마찬가지로 $A$의 row echelon form을 구하면 $O(log^2MAXVAL)$ 시간에 빠르게 판단할 수 있습니다.
1번과 같은 물음이 $Q$개 주어졌다고 하면, $O(QNlog^2MAXVAL)$ 시간에 답을 구할 수 있겠네요.
하지만 문제에서 주어진 벡터들이 고정인채로 $Q$개의 물음이 있는 경우에는 주어진 벡터들의 row echelon form이 고정이므로 한 번만 계산하면 됩니다.
따라서 총 $O(Nlog^2MAXVAL + Qlog^2MAXVAL)$ 시간에 구할 수 있습니다.
이 방법을 응용하면 아래와 같은 문제를 풀 수 있습니다.
[BOJ 11191 Xor Maximization]
이 문제는 위와 같은 조건에서 아래와 같은 문제에 답해야 합니다.
집합에 포함될 수 있는 원소의 최댓값을 구하기.
위에서 처럼 row echelon form을 구했다면 그리디한 방법으로 이 문제를 해결할 수 있습니다.
위에 있는 row 부터 보면 결과 벡터의 사전순서를 가장 크게 만들기 위해 이 row를 사용할지 말지를 결정할 수 있기 때문입니다.
따라서 이 문제는 $O(Nlog^2MAXVAL)$ 시간에 해결할 수 있습니다.
단, 64bit이하의 자연수에 대해 비트 연산이 O(1)에 동작하므로 아래의 코드는 $O(NlogMAXVAL)$ 시간에 동작합니다.
아래는 이 문제를 해결하는 코드입니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int N;
ll A[maxn];
vector<ll> basis;
int main() {
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%lld", &A[i]);
}
while(1) {
ll mx = *max_element(A, A + N);
if(!mx) break;
basis.push_back(mx);
for(int j = 0; j < N; j++) if((mx ^ A[j]) < A[j]) A[j] ^= mx;
}
ll ans = 0;
for(int i = 0; i < basis.size(); i++) if(ans < (ans ^ basis[i])) ans ^= basis[i];
printf("%lld", ans);
}
[BOJ 16685 XOR 포커]
이 문제는 위의 문제와 동일하지만 ‘짝수’개의 수를 사용하여야 한다는 조건이 있습니다.
우선 위와 같이 basis를 구해보도록 합시다.
각 basis 마다 원래 주어진 수들을 짝수개 사용한 것인지 홀수개 사용한 것인지 기록해 둡니다.
그 다음 위와 같이 그리디한 방법으로 최댓값을 구해봅시다.
이 때, 총 사용한 수의 개수가 짝수개라면 이 값을 출력하고 종료합니다.
만일 사용한 수의 개수가 홀수개라면 짝수개만 사용해서는 이 최댓값을 만들지 못할 수도 있습니다.
그렇기 때문에 이 경우는 잘 따져봐 주어야 합니다.
그러면 그리디한 방법으로 구한 사용한 수의 개수가 홀수개이더라도 짝수개를 사용해서 동일한 값을 만들 수 있는 경우는 어떤 경우일 까요?
바로 홀수개의 수로 0을 만들 수 있는 경우입니다.
이것이 필요충분 조건임을 쉽게 증명할 수 있습니다.
충분 조건임은 자명하고, 두 방식에 사용된 수들의 집합을 대칭차힙합한 결과 집합의 크기는 홀수이고, XOR 한 결과는 0일 것이기 때문입니다.
홀수개의 수의 XOR로 0을 만들 수 있는 지 알아보는 방법은 간단합니다.
우선 주어진 수들을 basis의 선형 결합으로 표현할 때, 원래 수를 홀수개 쓰는지 짝수개 쓰는지 기록합니다.
만일 짝수개 사용하는 경우가 있다면 이 경우는 홀수개의 수의 XOR로 0을 만들 수 있습니다.
그렇지 않다면 불가능합니다.
홀수개의 수의 XOR로 0을 만드는 것이 불가능한 경우, 즉, 짝수개의 수의 XOR로 위에서 계산한 최댓값을 만들지 못하는 경우에는 어떻게 해주어야 할까요?
이 경우에는 똑같이 그리디하게 진행하다가 basis 중 원래 수를 홀수개 사용하는 가장 작은 수의 결정을 반대로 해준다음 다시 그리디하게 진행하면 됩니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int N;
ll A[maxn];
int B[maxn], C[maxn];
vector<pair<ll, int> > basis;
ll ans;
int main() {
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%lld", &A[i]);
B[i] = 1;
}
int la = -1;
while(1) {
ll mx = 0;
int p = -1;
for(int i = 0; i < N; i++) if(!C[i] && mx < A[i]) {
mx = A[i];
p = i;
}
if(p == -1) break;
C[p] = 1;
if(B[p]) la = basis.size();
basis.push_back({ mx, B[p] });
for(int i = 0; i < N; i++) if(!C[i] && (A[i] ^ mx) < A[i]) {
A[i] ^= mx;
B[i] ^= B[p];
}
}
bool found = false;
for(int i = 0; i < N; i++) if(!A[i] && B[i]) {
found = true;
break;
}
if(found) {
for(int i = 0; i < basis.size(); i++) if(ans < (ans ^ basis[i].first)) ans ^= basis[i].first;
printf("%lld", ans);
}
else {
int cnt = 0;
for(int i = 0; i < basis.size(); i++) if(ans < (ans ^ basis[i].first)) {
ans ^= basis[i].first;
cnt ^= basis[i].second;
}
if(cnt % 2) {
ans = 0;
for(int i = 0; i < basis.size(); i++) {
if(i != la) {
if(ans < (ans ^ basis[i].first)) ans ^= basis[i].first;
}
else {
if(ans >= (ans ^ basis[i].first)) ans ^= basis[i].first;
}
}
}
printf("%lld", ans);
}
}
[BOJ 16904 집합과 쿼리]
이 문제는 추가 제거 연산이 반복적으로 주어질 때, 첫번째 문제를 여러번 푸는 것입니다.
오프라인으로 문제를 해결합시다.
각 수마다 그 수가 존재하는 시점(쿼리 번호 기준)의 구간들을 미리 구해 놓을 수 있습니다.
구간의 개수는 $O(Q)$ 개 일것입니다.
이제 $[1, Q]$ 의 시점들에 대한 분할 정복을 사용하여 이 문제를 해결할 수 있습니다.
분할 정복의 순서를 왼쪽 구간에서 오른쪽 구간을 처리하는 방식으로 잘 정해주면, 자신의 자식 구간에 대한 재귀를 호출할 때, 그 시점의 구간에서 전부 존재하는 수들에 대한 basis를 빠르게 갱신해 나갈 수 있습니다.
따라서 아래와 같은 코드로 해결 가능합니다.
시간 복잡도는 $O(QlogQlogMAXVAL)$ 입니다.
#include<bits/stdc++.h>
using namespace std;
int Q;
map<int, int> chk;
int V[31];
void store(int *tmp) {
for(int i = 0; i < 31; i++) tmp[i] = V[i];
}
void restore(int *tmp) {
for(int i = 0; i < 31; i++) V[i] = tmp[i];
}
void add(int v) {
for(int i = 30; i >= 0; i--) {
if(v & (1 << i)) {
if(V[i]) v ^= V[i];
else {
V[i] = v;
break;
}
}
}
}
int getMax() {
int ret = 0;
for(int i = 30; i >= 0; i--) if(ret < (ret ^ V[i])) ret ^= V[i];
return ret;
}
struct BIT {
vector<vector<int> > tree;
void init() {
tree = vector<vector<int> >(4 * Q);
}
void upd(int a, int b, int v, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n].push_back(v);
return;
}
int m = (l + r)>>1;
upd(a, b, v, l, m, 2*n);
upd(a, b, v, m + 1, r, 2*n + 1);
}
void dfs(int l, int r, int n) {
int tmp[31];
store(tmp);
for(int i = 0; i < tree[n].size(); i++) {
add(tree[n][i]);
}
if(l == r) {
cout << getMax() << '\n';
restore(tmp);
return;
}
int m = (l + r)>>1;
dfs(l, m, 2*n);
dfs(m + 1, r, 2*n + 1);
restore(tmp);
}
} bit;
int main() {
std::ios::sync_with_stdio(false);
cin >> Q;
bit.init();
for(int i = 0; i < Q; i++) {
int x; cin >> x;
x = abs(x);
if(chk[x]) {
bit.upd(chk[x] - 1, i - 1, x, 0, Q - 1, 1);
chk[x] = 0;
}
else chk[x] = i + 1;
}
for(auto it = chk.begin(); it != chk.end(); it++) {
if(it->second) {
bit.upd(it->second - 1, Q - 1, it->first, 0, Q - 1, 1);
}
}
bit.dfs(0, Q - 1, 1);
}