[BOJ 13710] XOR 합 3

https://www.acmicpc.net/problem/13710

13710번: XOR 합 3

 

- 문제 요약

 

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

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

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

 

 

- 알고리즘 정리

 

v[l-1]^v[r] = a[l]^a[l+1]^..a[r-1]^a[r]

수열 A가 주어질 때 각 요소를 이진수로 만들어준 다음 N번째 비트에 있는 1의 개수와 0의 개수를 구해서 두 수를 곱해주면 답을 구할 수 있습니다.

 

 

- 코드 작성

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
vector<int>v;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	v.resize(n+1);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		v[i]=v[i-1]^x;
	}
	vector<int>cnt(30);
    for(int i=0;i<30;i++){
    	for(int j=0;j<=n;j++){
    		if(v[j]&(1<<i)){
    			cnt[i]++;
			}
		}
	}
	ll result=0;
	for(int i=0;i<30;i++){
		result+=(1LL<<i)*cnt[i]*(n+1-cnt[i]);
	}
	cout<<result;
}

코드 제출 결과