| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 247 | 121 | 97 | 51.053% |
길이가 $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)$ 쌍의 개수를 출력한다.
4 1 2 1 2 3 1
1
10 5 7 1 7 3 6 0 2 5 6 4 8
3
4 3 7 2 5 2 5
4
9 4 3 5 7 9 11 13 15 17 19 21
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$이다.