[Gold I] XOR 합 3 - 13710

문제 링크

성능 요약

메모리: 26200 KB, 시간: 324 ms

분류

비트마스킹, 누적 합

제출 일자

2025년 2월 2일 03:55:42

문제 설명

수열의 XOR 합이란 수열에 들어있는 모든 원소를 다 XOR한 값이다.

수열 A 주어졌을 때, A의 모든 연속하는 부분 수열의 XOR 합을 더한 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 배열의 크기 N (1 ≤ N ≤ 100,000), 둘째 줄에는 수열 A에 들어있는 수가 주어진다. 수열 A에 들어있는 수는 109보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 A의 모든 연속하는 부분 수열의 XOR 합을 더한 값을 출력한다.

문제 풀이

XOR의 핵심 성질

• 같은 수를 두 번 XOR하면 0
• XOR은 순서가 바뀌어도 결과 동일

누적 XOR 배열 만들기

구간 [L,R]의 XOR 합 = refixSumXOR[R] ^ prefixSumXOR[L-1]

비트별로 계산하기

각 비트 위치에서:

1. 1의 개수 세기
2. 0의 개수 세기 (전체 개수 ( n+1 ) - 1의 개수)
   이 둘을 곱하면 그 비트에서 XOR 결과가 1이 되는 구간의 개수임

특정 자리에서 XOR결과가 1이려면 하나는 0이고 하나는 1이어야한다. 결국 0의 개수 × 1의 개수로 계산가능.

비트 위치 반영

각 비트별로:

1. 1이 되는 구간의 개수를 구하고
2. 그 비트의 값(2^i) 곱하기
3. 모든 비트에 대해 이 값을 더하기
   입력되는 수가 10^9 이하이므로 2^10이 1024인 점을 감안하여 2^30이 10억은 감당이 되므로 가능.

시간복잡도

누적 XOR 배열 만들기: O(N)
각 비트별로 1의 개수 세기: O(N 30)
최종 답 계산: O(30)
전체 시간 복잡도 = O(N 30)

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N;
    static long[] prefixSumXOR;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_13710_XOR합3/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        
        // 누적 XOR 배열 (XOR합 위해 0 포함)
        prefixSumXOR = new long[N+1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++){
            int a = Integer.parseInt(st.nextToken());
            prefixSumXOR[i] = prefixSumXOR[i-1] ^ a;
        }
        
        // 각 비트별 1 개수
        int[] oneCnt = new int[30];
        
        for(int i=0; i<30; i++){
            for(int j=0; j<=N; j++){
                if((prefixSumXOR[j] & (1L<<i)) != 0) oneCnt[i]++;
            }
        }
        
        long res = 0;
        for(int i=0; i<30; i++){
            // i번쨰 비트에서 : 1개수 x 0개수 x 2^i
            res += (1L<<i) * oneCnt[i] * (N+1-oneCnt[i]);
        }
        
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
        br.close();
    }
}