题目描述

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}$.

10 4
4 6 7 10

6

8 5
4 3 5 8 1

10

20 7
3 7 18 15 12 18 19

50

5 6
1 2 3 4 5 6

0

提示

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$