BOJ_13710_XOR 합 3 (Java)

[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에 들어있는 수는 10⁹보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 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();
    }
}