codeforces 563 div2 D - Ehab and the Expected XOR Problem (XOR, prefix xor)

https://codeforces.com/contest/1174/problem/D

xor문제는 기발한게 많은 것 같다.

 

<문제설명>

subsegment란, 맨 앞 혹은 맨 뒤 요소를 포함한 subarray이다.

 

n과 x를 입력받아서 숫자 배열을 하나 만든다 ( ai < (1<<n) ). 만든 배열은 길이가 1이상인 각각의 subsegment 요소를 모두 xor했을 때 0또는 x가 나오지 않도록 한다. 이때 배열의 길이를 최대가 되도록 하여라.

 

<풀이>

만든 배열의 요소들을 a1,a2,a3 ...라고 했을 때, subsegment들이 가질 수 있는 값들은 구간XOR[al,ar]이다.

 

prefix xor 배열을 b[1],b[2],b[3] ... 라고 하자. 구간XOR[al,ar] = b[r] XOR b[l-1] 이다.

 

이 값들(구간XOR)이 0이 되지 않도록 하려면 모든 bi값이 distinct면 된다.

어떤 b[r]값에 대해  b[r] XOR b[l-1] == x가 되도록 하는 b[l-1]값은 유일하다는 점을 이용하여 걸로준다.

 

위 조건에 맞춰서 가능한 b배열을 생성해 준 후 a[i] = b[i] xor b[i-1]임을 이용해서 a를 출력해준다.

 

b배열 만드는 로직을 좀 더 서술해보면,

1) 계산의 편의를 위해 b[0]=0이라고 생각한다. chk[x]를 미리 체크해둔다.

 

2) 1부터 (1<<n)-1까지의 숫자를 가능한 b의 값으로 차례로 넣어준다.

단, 이 때 chk[i^x]를 체크해준다. i^x는 i와 XOR하여 x가 되는 유일한 값이다.

 

<코드>

const int MAX = (1 << 18) + 5;

int main() {
	FAST;
	int n, x; cin >> n >> x;
    
	bool chk[MAX]{ 0 }; chk[x] = true;
	vector<int> b;
    
	b.push_back(0);
	for (int i = 1; i < (1 << n); i++) {
		if (chk[i]) continue;
		chk[i^x] = true;
		b.push_back(i);
	}
    
	cout << b.size() - 1 << '\n';
	for (int i = 1; i < b.size(); i++) 
		cout << (b[i] ^ b[i - 1]) << " \n"[i == b.size() - 1];
	
}

 

<생각>

원본 배열보다 prefix array를 먼저 생각해야 하는 문제였다.