XOR 쌍

면접 대비

시간 제한1초메모리 제한1024 MB

요약

A, B, A⊕B가 1 이상 N 이하이고 A와 B가 각각 A⊕B 이하이며 A⊕B가 집합 S에 없는 순서쌍 (A, B)의 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 비트 연산, 수학, 해시맵
정답자: 아직 제출이 없습니다

문제

XOR은 대응하는 입력 비트가 서로 다를 때에만 결과 비트를 1로 만드는 비트 연산자이다. 즉 한쪽은 1이고 다른 쪽은 0인 경우이다. XOR 연산자는 보통 기호 $\oplus$ 로 쓰며, 대부분의 프로그래밍 언어에서는 ^(캐럿) 문자로 쓴다. 예를 들어 $(10 \oplus 6) = 12$ 이다.

10 =>  1010
 6 =>  0110
      ----- ⊕
       1100   => 12

이 문제에서는 정수 $N$ 과 정수 집합 $S_1, \ldots, S_M$ 이 주어진다. $1 \le A, B \le (A \oplus B) \le N$ 을 만족하고 $(A \oplus B) \notin S_1, \ldots, S_M$ 인 순서쌍 $(A, B)$ 의 개수를 세어라.

예를 들어 $N = 10$ 이고 $S = \{4, 6, 7, 10\}$ 이라고 하자. 조건을 만족하는 $(A, B)$ 쌍은 6개이다.

$(1, 2)$ → $(1 \oplus 2) = 3$
$(1, 4)$ → $(1 \oplus 4) = 5$
$(1, 8)$ → $(1 \oplus 8) = 9$
$(2, 1)$ → $(2 \oplus 1) = 3$
$(4, 1)$ → $(4 \oplus 1) = 5$
$(8, 1)$ → $(8 \oplus 1) = 9$

$(2, 4)$ 는 조건을 만족하지 않는다. $(2 \oplus 4) = 6$ 이고 $6 \in S$ 이기 때문이다. $(5, 1)$ 도 $A, B \le (A \oplus B)$ 를 어기므로 조건을 만족하지 않는다.

입력

첫 줄에 정수 $N$ 과 $M$ 이 주어진다( $1 \le N \le 10^6$ , $1 \le M \le 100\,000$ ). $N$ 은 주어진 상한이고, $M$ 은 집합 $S_1, \ldots, S_M$ 의 크기이다. 다음 줄에는 집합의 원소인 정수 $S_i$ 가 $M$ 개 주어진다( $1 \le S_i \le 10^6$ ).

출력

$1 \le A, B \le (A \oplus B) \le N$ 을 만족하고 $(A \oplus B) \notin S_1, \ldots, S_M$ 인 $(A, B)$ 쌍의 개수를 한 줄에 출력한다.

예제4

예제 1
입력
```
10 4
4 6 7 10
```
예상 출력
```
6
```
예제 2
입력
```
8 5
4 3 5 8 1
```
예상 출력
```
10
```
예제 3
입력
```
20 7
3 7 18 15 12 18 19
```
예상 출력
```
50
```
예제 4
입력
```
5 6
1 2 3 4 5 6
```
예상 출력
```
0
```