📝 문제 정보#
🧐 관찰 및 접근#
- bitwise and들의 합과, 합들의 bitwise and 값을 구해야한다.
- 일단 앞에껏부터 해보자. $N$은 100만??이다. 개크네
- 모든 $(A_i \& B_j)$의 합을 1999로 나눈 나머지
- 나이브하게 제곱은 될 리가 없다.
- bitwise and의 특성을 생각해보자. $A_i$에서도, $B_j$에서도 켜져있어야 한다.
- 각 비트에 대해서 생각하면, $A$에서 해당 비트가 켜진 개수 * $B$에서 해당 비트가 켜진 개수와 같이 구할 수 있을 것 같다.
- 전처리에 $O(N\times29)$, 계산하는데에 $O(29)$가 걸릴 것 같다.
- 모든 $(A_i + B_j)$의 bitwise and 연산 값
- 자 이제 이게 문젠거같은데… 합이 이슈다. 받아올림이 있다보니 조금 신경쓰인다.
- 다시한번 bitwise and의 특성을 생각해보자. 모두 켜져있어야 한다는건, 모든 순서쌍 $(i, j)$에 대해 $A_i + B_j = C_k$라고 할때, 어떤 $C_k$의 비트가 꺼져있으면, 정답에서 해당 비트는 꺼진다.
- 일단 첫번째 비트에 대해서는 쉽게 구할 수 있는 것 같다. 더했을때 모두 $1$이 남기 위해선 $1 + 0, 0 + 1$ 두가지만 가능하기에, 개수가 $(N, 0), (0, N)$이 아니라면 비트가 꺼질 수밖에 없다.
- 하지만 해당 윗 비트부터는 받아올림이 생긴다… $11_2 + 01_2 = 100_2$ 와 같이 $(1, 0)$이었음에도 비트가 꺼질 수 있다. 혹은 $11_2 + 11_2 = 110_2$와 같이 $(1, 1)$이었으메도 비트가 켜질 수 있다.
- 하 이게 무슨 의미지? 예를들어 $4$의자리 비트가 켜져있나? 라는 질문은 $8$로 나눈 나머지들의 합에 대해, 나머지가 모두 $4$ 이상인가? 하는 질문과 같긴 하다. $0$
$3$, $8$$11$은 안된다는거지. 그 사이에 값이 있는지 없는지를 체크할 수가 있나?- 일반화시키면, $2^k$의 비트가 켜져있는건 $\mod 2^{k+1}$ 에 대해 나눈 애들의 합에 대해 $0 \leq s < 2^k$ 또는 $2^{k+1} \leq s < 2^{k+1} + 2^k$ 인게 있으면 안된다.
- 이걸 각 비트에 대해 한다고 하면 그래도 정렬해서 이분탐색으로 구할 순 있을거같긴 한데…… $N$ 제한이 100만이라 $O(29 \times N\log{N})$을 하면 죽여버리겠다는 말과 같은 것 같다.
- 어? 근데 내가 필요한건, 비트단위로 하나씩 확장해나가면서 정렬하는거다. 이게 바로 Radix Sort 아닌가?
- 게다가 배열 두개로 쪼개져있을때, 다른 배열에서 하나하나 합이 저 안에 들어있는지 확인하는건 그리디하게 0/1로 쪼개진 두 배열의 맨앞/맨뒤를 보는것만으로 해결할 수 있는 것 같다. 덱을 이용해서 관리해보자.
💻 풀이#
- 코드 (C++):
void solve(){
ll N; cin >> N;
vector<ll> A(N), B(N);
rep(i, 0, N) cin >> A[i];
rep(i, 0, N) cin >> B[i];
vector<ll> bitCountA(30), bitCountB(30);
rep(i, 0, N) rep(j, 0, 30){
if((A[i] >> j) & 1) bitCountA[j]++;
if((B[i] >> j) & 1) bitCountB[j]++;
}
ll ans1 = 0;
rep(i, 0, 30){
ans1 += (1LL << i) % 1999 * (bitCountA[i] * bitCountB[i]) % 1999;
ans1 %= 1999;
}
cout << ans1 << " ";
ll ans2 = 0;
vector<ll> dq[2], ndq[2];
dq[0].reserve(N);
dq[1].reserve(N);
ndq[0].reserve(N);
ndq[1].reserve(N);
rep(i, 0, N) dq[0].push_back(A[i]);
rep(bit, 0, 30){
ndq[0].clear();
ndq[1].clear();
for(ll x: dq[0]) (x >> bit) & 1 ? ndq[1].push_back(x) : ndq[0].push_back(x);
for(ll x: dq[1]) (x >> bit) & 1 ? ndq[1].push_back(x) : ndq[0].push_back(x);
swap(dq[0], ndq[0]);
swap(dq[1], ndq[1]);
vector<ll> cand;
if(!dq[0].empty()){
cand.push_back(dq[0].front());
cand.push_back(dq[0].back());
}
if(!dq[1].empty()){
cand.push_back(dq[1].front());
cand.push_back(dq[1].back());
}
bool flag = true;
for(auto x: B) for(auto c: cand) if((((x+c) >> bit) & 1) == 0){
flag = false;
break;
}
if(flag) ans2 += (1LL << bit);
}
cout << ans2 << "\n";
}