P15603 [ICPC 2021 Jakarta R] XOR Pairs

XOR is a bitwise operator that evaluates the resulting bit into 1 if and only if their corresponding input bits differ (one of them is 1 while the other is 0). XOR operator is usually written with a symbol $\oplus$, or in most programming languages, the character ^ (caret). For example, $(10 \oplus 6) = 12$. $$ \begin{aligned} 10\ &=>\ \ \ 1010 \\ 6\ &=>\ \ \ 0110 \\ \quad\ &----\ \oplus \\ \quad\ & \quad \quad \quad 1100\ \ =>\ 12 \\ \end{aligned} $$ In this problem, you are given an integer $N$ and a set of integers $S_{1..M}$. Your task is to count how many pairs of integers $\langle A, B \rangle$ such that $1 \leq A, B \leq (A \oplus B) \leq N$, and $(A \oplus B) \notin S$. For example, let $N = 10$ and $S_{1..4} = \{4, 6, 7, 10\}$. There are 6 pairs of $\langle A, B \rangle$ that satisfy the condition. - $\langle 1, 2 \rangle \rightarrow (1 \oplus 2) = 3$ - $\langle 1, 4 \rangle \rightarrow (1 \oplus 4) = 5$ - $\langle 1, 8 \rangle \rightarrow (1 \oplus 8) = 9$ - $\langle 2, 1 \rangle \rightarrow (2 \oplus 1) = 3$ - $\langle 4, 1 \rangle \rightarrow (4 \oplus 1) = 5$ - $\langle 8, 1 \rangle \rightarrow (8 \oplus 1) = 9$ Observe that a pair such as $\langle 2, 4 \rangle$ does not satisfy the condition for this example as $(2 \oplus 4) = 6$ but $6 \in S$. Another pair such as $\langle 5, 1 \rangle$ also does not satisfy the condition as it violates the requirement $A, B \leq (A \oplus B)$.

Input begins with a line containing two integers $N$ $M$ ($1 \leq N \leq 10^6$; $1 \leq M \leq 100\,000$) representing the given $N$ and the size of the set of integers $S_{1..M}$. The next line contains $M$ integers $S_i$ ($1 \leq S_i \leq 10^6$) representing the set of integers $S_{1..M}$.

Output contains an integer in a line representing the number of $\langle A, B \rangle$ such that $1 \leq A, B \leq (A \oplus B) \leq N$ and $(A \oplus B) \notin S_{1..M}$.

#### Explanation for the sample input/output #1 This is the example from the problem description. #### Explanation for the sample input/output #2 There are 10 pairs of $\langle A, B \rangle$ that satisfy the condition. - $\langle 1, 6 \rangle \rightarrow (1 \oplus 6) = 7$ - $\langle 2, 4 \rangle \rightarrow (2 \oplus 4) = 6$ - $\langle 2, 5 \rangle \rightarrow (2 \oplus 5) = 7$ - $\langle 3, 4 \rangle \rightarrow (3 \oplus 4) = 7$ - $\langle 3, 5 \rangle \rightarrow (3 \oplus 5) = 6$ - $\langle 4, 2 \rangle \rightarrow (4 \oplus 2) = 6$ - $\langle 4, 3 \rangle \rightarrow (4 \oplus 3) = 7$ - $\langle 5, 2 \rangle \rightarrow (5 \oplus 2) = 7$ - $\langle 5, 3 \rangle \rightarrow (5 \oplus 3) = 6$ - $\langle 6, 1 \rangle \rightarrow (6 \oplus 1) = 7$