백준 33901 (C++) OR이 아니면? XOR

최초 업로드: 2025-11-15 13:31:47

최근 수정 시간: 2025-11-15 13:31:47

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] OR이 아니면? XOR

[문제 링크](https://www.acmicpc.net/problem/33901)

## 문제 설명

길이가 $N$인 정수 수열 $A$와 정수 $M$, $K$가 주어질 때, 아래 조건을 만족하는 $(i, j)$ 쌍의 개수를 구하시오.

$A_i$는 $A$의 $i$번째 원소를 의미한다.

## 입력

첫 번째 줄에 수열의 길이 $N$, $M$, $K$가 주어진다. $(2 \le N \le 10^6;$ $1 \le M \le N - 1;$ $0 \le K \le 2^{17} - 1)$

두 번째 줄에 수열 $A$의 원소 $A_i$가 공백으로 구분되어 $N$개 주어진다. $(0 \le A_i \le 100\,000)$

## 출력

첫 번째 줄에 조건을 만족하는 $(i, j)$ 쌍의 개수를 출력한다.

## 풀이
A[i]와 K를 XOR시킨 값은 하나이기 때문에 슬라이딩 윈도우로, 크기 M+1짜리 윈도우 내의 모든 원소를 기록하며 매번 A[i]^K의 개수를 세면 됩니다.

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

int a[1'000'000], total[1<<17];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m, k; cin >> n >> m >> k;
 for(int i=0;i<n;i++) cin >> a[i];

long long cnt=0, right=0;
 while(right<=m) total[a[right++]]++;
 for(int i=0;i<n;i++) {
 total[a[i]]--;
 cnt += total[a[i]^k];
 if(right<n) total[a[right++]]++;
 }
 cout << cnt;
}
```