시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB2471219751.053%

문제

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

  1. $A_i ⊕ A_j$ = $K$
  2. $j - i$ $\le$ $M$ $(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)$ 쌍의 개수를 출력한다.

예제 입력 1

4 1 2
1 2 3 1

예제 출력 1

1

예제 입력 2

10 5 7
1 7 3 6 0 2 5 6 4 8

예제 출력 2

3

예제 입력 3

4 3 7
2 5 2 5

예제 출력 3

4

예제 입력 4

9 4 3
5 7 9 11 13 15 17 19 21

예제 출력 4

0

힌트

음이 아닌 두 정수 $A$, $B$의 배타적 논리합 $A ⊕ B$는 다음과 같이 정의된다.

이진법으로 생각했을 때, $A$의 $2^k$의 자릿수와 $B$의 $2^k$의 자릿수가 서로 다르면 $A ⊕ B$의 $2^k$의 자릿수가 $1$이고, 같으면 $A ⊕ B$의 $2^k$의 자릿수가 $0$이다. (단, $k \geq 0$)

예를 들어 $12 ⊕ 10$은 $12$ = $1100_{(2)}$, $10$ = $1010_{(2)}$이므로 $1100_{(2)} ⊕ 1010_{(2)}$ = $0110_{(2)}$ = $6$이다.