[BOJ/C++] 15896. &+ +&

문제 : https://www.acmicpc.net/problem/15896

15896번: &+ +&

 

1. 설명

길이가 N인 수열 $A_1 , ... , A_N$ 과 $B_1 , ... , B_N$이 있습니다.

$1 \le i,j \le N$인 모든 $i, j$에 대한 $A_i \cap B_j$ 의 합과 $A_i + B_j$의 & (bitwise AND) 연산 값을 구해야 합니다.

첫 번째 값의 경우 1999로 나눈 나머지를 구해야 합니다.

 

2. 풀이

bitwise 연산을 사용하니, 각각의 비트에 대한 값이 어떻게 나오는지 알아봅시다.

 

1] 모든 $A_i \cap B_j$ 의 합

bitwise AND는 두 비트 모두 1인 경우에만 1이 됩니다.

그러므로 결과값의 k번째 비트값이 1이려면 $A_i$의 k번째 비트값과 $B_j$의 k번째 비트값 모두 1이어야 합니다.

따라서 k번째 비트값이 1인 $A_i + B_j$ 항의 개수는

$cntA_k \times cntB_k$ 임을 알 수 있습니다.

($cntA_k$는 수열 A에서 k번째 비트가 1인 수의 개수, $cntB_k$는 수열 B에서 k번째 비트가 1인 수의 개수)

 

정리하면, 첫 번째 값은

$$\sum^N_{k=0} 2^k \times cntA_k \times cntB_k$$

으로 구할 수 있습니다.

각각의 수열 값 $x$에 대해 $x \cap 2^k$이 0인지 아닌지를 판단하여 k번째 비트의 개수를 셀 수 있습니다.

 

계산하는 값의 증가폭이 크기 때문에, 모듈러 연산을 잘 처리해줘야 합니다.

 

2] 모든 $A_i + B_j$의 bitwise AND

두 번째 값의 경우엔 덧셈 연산에 따라 비트 값이 달라질 수 있으므로 다르게 접근해야 합니다.

마찬가지로 k번째 비트를 기준으로 살펴봅시다.

 

두 수를 더할 때 k번째 비트값이 변하는 데 영향을 줄 수 있는 건 0 ~ k번째 비트입니다.

k + 1번째 비트부터는 더하더라도 하위 비트가 바뀌지 않으므로, 이 부분을 제외시키도록 합시다.

 

위에서 그러했듯이, 우리가 구하는 값은 bitwise AND 연산을 적용한 값이므로

k번째 비트가 0이 되느냐를 알아야 합니다.

모든 $A_i + B_j$ 중에 하나라도 k번째 비트가 0인 값이 존재한다면, 결과값의 k번째 비트는 0이 되기 때문입니다.

다만 항의 개수가 $N^2 \le 10^{12}$개 이므로, 모든 경우를 직접 확인해 보는 것은 너무 오래 걸립니다.

 

그럼 어떤 경우에 k번째 비트가 0이 되는지 생각해봅시다.

 

k번째 비트보다 하위에 있는 비트들의 합을 $sum$이라고 하겠습니다.

두 수의 k번째 비트가 0이고 $sum < 2^k$ (하위 비트를 더해서 1이 넘어오지 않는 경우입니다)

두 수의 k번째 비트가 1이고 $sum < 2^k$

한 쪽만 k번째 비트가 1이고 $sum \ge 2^k$ (1이 넘어오는 경우)

 

정도로 볼 수 있습니다. 각각을 case 1, 2, 3으로 살펴봅시다.

 

case 1]

    0[XXXXXXXXX...] = $a \in A$

 + 0[YYYYYYYYYY...] = $b \in B$

----------------------

    0[ZZZZZZZZZZ...]

 

여기서 a, b는 원래 값에서 앞부분부터 k + 1번째 비트까지를 날리고 k번째 비트부터 표현했습니다.

앞서 말했듯이 k + 1번째 비트까지는 영향을 주지 않기 때문입니다.

실제로 계산하는 비트 또한 k - 1번째 비트부터니 a와 b를 다음과 같이 마스킹할 수 있습니다.

$mask = 2^k - 1$이라 할 때, $a = a \cap  mask, b = b \cap  mask$

 

중요한 것은 위 조건을 만족하는 (a, b) 쌍이 하나라도 있느냐 입니다.

따라서 위 조건을 만족하는 최소한의 경우가 무엇인지 알면 됩니다.

 

조건을 만족하는 a와 b가 존재한다면,

k번째 비트가 0인 수열 A, B의 값 중 최솟값 $a_{min} , b_{min}$에 대해서도 조건이 성립함을 알 수 있습니다.  -> $a_{min} + b_{min} < 2^k$

 

$a_{min} + b_{min} \ge 2^k$인 경우, k번째 비트가 0인 모든 $a , b$에 대해 $a + b \ge 2^k$이기 때문입니다.

k번째 비트가 0이란 말은 $a < 2^k , b < 2^k$ 임을 말하므로 $2^k \le a + b < 2^{k+1}$,

따라서 합의 k번째 비트가 반드시 1이 된다는 것을 말합니다.

 

그래서 $(a_{min} + b_{min}) \cap 2^k$가 0인지를 판단하면 case 1에서 k번째 비트가 0이 되는 경우가 존재하는지 판단할 수 있습니다.

 

case 2]

    1[XXXXXXXXX...] = $a \in A$

 + 1[YYYYYYYYYY...] = $b \in B$

----------------------

 [E]0[ZZZZZZZZZZ...]

 

case 1과 마찬가지로, $a_{min} + b_{min}$을 판단하면 됩니다.

최상위 비트가 1인 것은 중요하지 않습니다. case 1에서 설명했듯이, k번째 비트까지는 계산에 상관 없으므로 마스킹했기 때문입니다.

따라서 [E]가 판단에 영향을 주지 않으니 case 1과 똑같다는 걸 알 수 있습니다.

 

case 3]

    1[XXXXXXXXX...] = $a \in A$

 + 0[YYYYYYYYYY...] = $b \in B$

----------------------

 [E]0[ZZZZZZZZZZ...]

 

먼저 a의 k번째 비트가 1이라고 가정하고 진행합니다.

앞부분부터 k번째 비트까지 계산했을 때 k번째 비트의 결과값이 1이므로,

최종 결과가 0이 되는 경우는, $a + b \ge 2^k$인 경우입니다.

 

이러한 a, b가 존재한다면, k번째 비트가 1인 수열 A의 최댓값 $a_{max}$와 k번째 비트가 0인 수열 B의 최댓값 $b_{max}$에 대해서도 식이 성립합니다.

그렇지 않다면 case 3에서 힙의 k번째 비트가 0이 되는 경우는 존재하지 않습니다.

case 1, 2와 부등호 방향이 반대라는 점에서도 유추할 수 있습니다.

 

그래서 $(a_{max} + b_{max}) \cap 2^k$가 0인지를 판단하면 됩니다.

이는 b의 최상위 비트가 1인 경우에도 동일하게 적용됩니다.

 

정리]

수열 A, B에서 k번째 비트가 0인 수 중 최솟값과 최댓값, k번째 비트가 1인 수 중 최솟값과 최댓값을 구합니다.

이를 각각 $a_{min0} , a_{max0}, a_{min1} , a_{max1}$과 $b_{min0} , b_{max0}, b_{min1} , b_{max1}$이라 하겠습니다.

다음 조건을 하나라도 만족하면 결과값의 k번째 비트를 0으로 설정합니다.

그렇지 않으면 결과값의 k번째 비트는 1입니다.

 

$a_{min0} , b_{min0}$ 둘 다 존재하고, $(a_{min0} + b_{min0}) \cap 2^k = 0$

$a_{min1} , b_{min1}$ 둘 다 존재하고, $(a_{min1} + b_{min1}) \cap 2^k = 0$

$a_{max0} , b_{max1}$ 둘 다 존재하고, $(a_{max0} + b_{max1}) \cap 2^k = 0$

$a_{max1} , b_{max0}$ 둘 다 존재하고, $(a_{max1} + b_{max0}) \cap 2^k = 0$

 

$1 \le a , b \le 2^{28}$ 이므로, 최소 29개의 비트값을 계산해야 합니다.

 

3. 코드

#include <iostream>
#include <algorithm>

using namespace std;

const int MOD = 1999;
int N, A[1000001], B[1000001], m = 0, M = 1 << 30;
int bitA[31], bitB[31], ans1, x;
int minA[31][2], minB[31][2], maxA[31][2], maxB[31][2], ans2, y;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 30; i++)
		for (int j = 0; j < 2; j++)
		{
			minA[i][j] = minB[i][j] = M;
			maxA[i][j] = maxB[i][j] = m;
		}

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];

		x = A[i];
		for (int j = 0; j < 30; j++, x >>= 1) if (x & 1) bitA[j]++;
	}

	for (int i = 0; i < N; i++)
	{
		cin >> B[i];

		x = B[i];
		for (int j = 0; j < 30; j++, x >>= 1) if (x & 1) bitB[j] = (bitB[j] + bitA[j]) % MOD;
	}

	int mask = 1;
	for (int i = 0; i < 30; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int firstA = 0, firstB = 0;
			if (A[j] & (1 << i)) firstA = 1;
			if (B[j] & (1 << i)) firstB = 1;

			minA[i][firstA] = min(minA[i][firstA], A[j] & mask);
			maxA[i][firstA] = max(maxA[i][firstA], A[j] & mask);
			minB[i][firstB] = min(minB[i][firstB], B[j] & mask);
			maxB[i][firstB] = max(maxB[i][firstB], B[j] & mask);
		}
		mask = (mask << 1) | 1;
	}

	for (int i = 0; i <= 28; i++)
	{
		ans1 += ((1 << i) % MOD * bitB[i]) % MOD;
		ans1 %= MOD;
	}

	ans2 = (1 << 30) - 1;
	mask = 1;

	for (int i = 0; i < 30; i++, mask <<= 1)
	{
		if (minA[i][0] != M && minB[i][0] != M && ((minA[i][0] + minB[i][0]) & mask) == 0)
			ans2 &= ~mask;
		if (minA[i][1] != M && minB[i][1] != M && ((minA[i][1] + minB[i][1]) & mask) == 0)
			ans2 &= ~mask;
		if (maxA[i][1] != m && maxB[i][0] != m && ((maxA[i][1] + maxB[i][0]) & mask) == 0)
			ans2 &= ~mask;
		if (maxA[i][0] != m && maxB[i][1] != m && ((maxA[i][0] + maxB[i][1]) & mask) == 0)
			ans2 &= ~mask;
	}
	
	cout << ans1 << ' ' << ans2;
	return 0;
}