cf 626 div2 D - present (수론, 이분탐색)

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

어렵지만 여기저기서 출제된 적이 있는 문제. 핵심 아이디어는 가져가자

 

<문제설명>

최대 4e5개의 원소 n개를 갖는 배열이 있다. 원소는 1e7이하의 자연수를 갖는다.

 

n개 중 2개 원소의 가능한 모든 쌍에 대해 합을 구해 모두 xor한 값을 구해라

 

(a1+a2)⊕(a1+a3)⊕  …  ⊕(a1+an)⊕(a2+a3)⊕  …  ⊕(a2+an)…⊕(an−1+an)

 

<풀이>

한 쌍의 합의 최댓값은 2e7이므로 답을 ans라 했을때 ans는 24개 비트로 표현 가능하다.

 

ans의 k번째 비트가 켜져있는지 nlogn에 알 수 있다.

 

 

a의 원소들은 k+1번 이후의 비트는 k번째 비트에 영향을 주지 않는다.

 

b <- a % ( 1<< (k+1) );  b오름차순 정렬

 

b[i]와 짝을 이뤄 k번째 비트를 켜주는 쌍의 수를 모든 i에 대해 구해 더해준 값을 cnt라 하자

 

cnt가 홀수면 ans의 k번째 비트가 켜져 있는 것이다.

 

 

b[i]와 짝을 이뤄 k번째 비트를 켜주는 쌍의 수는 어떻게 구할까?

 

예를들어 k=4라고 하자. 구간[0,1000] 사이의 두 값을 더해서 4번째 비트가 켜져있는 경우는

1) 1000 ~ 1111

2) 11000 ~ 11111 

위 두가지 경우 뿐이다.

 

구간[0, (1<<k)] 사이의 값을 갖는 두 개 정수를 저해서 k번째 비트를 켜주는 경우는 두 합이

1) [(1<<k),(1<<(k+1))-1]

2) [(1<<(k+1)) + (1<<k) , (1<<(k+2))-1]

둘 중 하나의 구간에 속해야 한다.

 

b는 정렬돼 있고 원하는 값이 연속된 구간을 이루므로 cnt를 각각의 i에 대해 logn에 구할 수 있다.

 

<코드>

int n;
ll ans;
vector<int> a,b;
int main() {
	FAST; cin >> n;
	a.resize(n); b.resize(n);
	for (int i = 0; i < n; i++) 
		cin >> a[i];
	
	for (int k = 0; k <= 24; k++) {
		for (int i = 0; i < n; i++)
			b[i] = a[i] % (1 << (k + 1));
		sort(b.begin(), b.end());

		int cnt = 0;
		for (int i = 0; i < n-1; i++) {
			int k1 = (1 << (k)), k2 = (1 << (k + 1)), k3=(1<<(k+2));
			auto bi = b.begin(), ei = b.end();
			cnt += lower_bound(bi + i + 1, ei, k2 - b[i])
				   - lower_bound(bi + i + 1, ei, k1 - b[i]);
					
			cnt += lower_bound(bi + i + 1, ei, k3-1 - b[i])
				   - lower_bound(bi + i + 1, ei, k1+k2 - b[i]);
		}
		if (cnt % 2) ans += (1 << k);	//ans의 k번째 비트를 켜준다
	}
	cout << ans << '\n';
}