XOR 문제에 접근하기 위해 반드시 필요한 스킬3 -모든 쌍의 XOR의 합(sum of all pair of xor)-

1. 모든 원소 쌍의 XOR 합

 

$A_{0}, A_{1}, ... , A_{n-1}$에 대하여 $\sum_{i=0}^{i=n-1} \sum_{j=i+1}^{j=n-1} A_{i} \oplus A_{j}$을 구하는 문제

 

단순하게 풀면 $O(N^{2})$이지만 조금 더 생각해본다면 $O(N)$에 가깝게 해결할 수 있다.

 

결국 구하고자 하는 값은 $V = A_{i} \oplus A_{j}$라고 할 때, 이 V들의 합이다.

 

그런데 V를 2진수로 나타낸다면..

 

$$V = a_{k}2^{k} + a_{k-1}2^{k-1} + ... + a_{1}*2 + a_{0}$$로 나타낼 수 있다.

 

여기서 $a_{i} = 0$이거나 $a_{i} = 1$이다.

 

만약 모든 $V = A_{i} \oplus A_{j}$에 대하여 최대로 큰 비트가 k라고 한다면...

 

구하고자 하는 값은 모든 V를 2진수로 나타내서 더한다면...

 

$$(a_{1}+b_{1}+c_{1}+...)2^{k} + (a_{2}+b_{2}+c_{2}+...)2^{k-1} + ... + (a_{k}+b_{k}+...)*2 + (a_{k+1}+b_{k+1}+...)$$ 형태로 나타난다.

 

여기서 모든 a,b,c는 0이거나 1이다.

 

그래서 조금 다르게 접근해서 결과값의 0,1,2,3,..,k번째 비트에 어떤 값이 들어갈지를 결정한다면...

 

즉, 0,1,2,3,...,k번째 부분에 a,b,c,..값들을 결정하는 방법으로 접근한다면 적어도 $O(N)$보다는 $O(K)$로 줄어든다.

 

여기서 두 수 $A_{i}$와 $A_{j}$의 XOR은 어떻게 구해질까?

 

$A_{i}$와 $A_{j}$를 2진수로 나타내서 

 

1010000101010101....

 

0100010010001110....

 

각 비트끼리 비교해서 비트가 서로 다르면 1이고 비트가 서로 같으면 0이다.

 

그러므로 k번째 비트에 대하여

 

$A_{i}$의 k번째 비트가 1이면.. $A_{j}$의 k번째 비트가 0인 경우와 XOR했을때 전체 합의 k번째 비트에 1이 들어간다.

 

$A_{i}$의 k번째 비트가 0이면.. $A_{j}$의 k번째 비트가 1인 경우와 XOR했을때 전체 합의 k번째 비트에 1이 들어간다.

 

그래서 k=0,1,2,...K 번째 비트에 대하여...

 

배열 A를 순회하여 k번째 비트가 1인 원소의 수 * k번째 비트가 0인 원소의 수가 전체 합의 k번째 비트에 들어가는 1의 개수이다.

 

이제 전체 합의 각 k번째 비트에 들어가는 1의 개수를 찾았다.

 

그 개수에 $2^{k}$를 곱해주면 결과를 10진수로 바꿀 수 있다.

 

2. 연습문제

 

13710번: XOR 합 3 (acmicpc.net)

13710번: XOR 합 3

 

 

3. 풀이

 

A의 모든 연속하는 부분수열의 XOR합을 구하는 문제

 

연속하는 부분수열의 XOR합은... $A_{0} \oplus A_{1} \oplus...\oplus A_{i}$를 모두 구해놓은 배열 V를 먼저 구한다.

 

그리고 배열 V에서 두 원소 $V_{i}$와 $V_{j}$의 XOR이 i+1 ~ j까지 연속하는 부분수열의 XOR합임을 알고 있다.

 

https://deepdata.tistory.com/1091

XOR 문제에 접근하기 위해 반드시 필요한 스킬2 - 연속하는 부분열의 XOR-

 

 

따라서 먼저 배열 V를 구하고, 배열 V에서 위에서 설명한 알고리즘대로 구현한다.

 

여기서 A에 들어있는 원소의 값이 최대 $10^{9}$인데 이게 2진수로 30비트이다.

 

그래서 배열 V의 원소도 최대 30비트정도이다.

 

따라서 k=0~30까지에 대하여.. 배열 V에서 k번째 비트가 1인 원소의 수를 센다.

 

어떤 수의 k번째 비트가 1인지 0인지 알아내는 방법은?

 

v & (1 << k)로 찾을 수 있다.

 

https://deepdata.tistory.com/492

비트마스킹을 위한 비트연산 필수이론 가볍게 정리

 

여기서 만약 k번째 비트가 1인 원소의 수가 x개라면, 배열 V의 원소가 len(V)개이므로 k번째 비트가 0인 원소의 수는?

 

len(V)-x로 바로 구할 수 있다.

 

따라서 전체 합에서.. $(a+b+c+...+)*2^{k}$ 부분에서 (a+b+c+...+)에 해당하는 부분은...

 

x * (len(V) - x)로 구할 수 있다.

 

여기에 $2^{k}$를 곱해주면 10진수로 바꿀 수 있다.

 

이를 모든 k = 0,1,2,..,30에 대해 반복해준다면 된다.

 

#모든 연속하는 부분수열의 XOR을 더한 값
n = int(input())

A = list(map(int,input().split()))

#연속하는 부분수열의 XOR을 구하기 위해
#V배열 V0 = 0, Vi = A0 ^ A1 ^ A2 ^...^Ai를 구해놓는다.
V = [0,A[0]]

for i in range(1,n):
    
    V.append(V[-1]^A[i])

#A의 원소가 최대 10^9로 2진수로 바꾸면 30비트
#구하고자하는 값을 2진수로 나타낸다면..
#(a+b+c+...)2^k + (d+e+f+...)2^k-1 + ... + (x+y+z+...)*2 + (p+q+r+...)
#k번째 비트에 주목해서 각 비트가 1인 원소의 개수를 세면 된다.
#두 원소의 XOR로 비트가 1일려면 두 원소의 k번째 비트가 서로 달라야한다.
#따라서 전체 합의 k번째 비트 = (A의 k번째 비트가 0인 원소의 수) * (A의 k번째 비트가 1인 원소의 수)
bit = [0]*31

for k in range(31):
    
    for v in V:
        
        if v & (1 << k): #v의 k번째 비트가 1인지 0인지 판단하는 방법
            
            bit[k] += 1

#각 비트별로 1인 원소의 개수를 모두 찾았다면...
#(비트가 1인 개수) * 2^{k}를 모든 k=0,1,2,..에 대해 더하면 10진수로 바꿀 수 있다.
answer = 0

for i in range(31):
    
    answer += (bit[i]*(len(V)-bit[i])*(2**i))

print(answer)