P15603 [ICPC 2021 Jakarta R] XOR Pairs

XOR 是一种按位运算符，当且仅当对应的输入位不同（一个为 1 而另一个为 0）时，结果的该位为 1。XOR 运算符通常用符号 $\oplus$ 表示，在大多数编程语言中则用字符 ^（脱字符）表示。例如，$(10 \oplus 6) = 12$。 $$ \begin{aligned} 10\ &=>\ \ \ 1010 \\ 6\ &=>\ \ \ 0110 \\ \quad\ &----\ \oplus \\ \quad\ & \quad \quad \quad 1100\ \ =>\ 12 \\ \end{aligned} $$ 本题中，给定一个整数 $N$ 和一个整数集合 $S_{1..M}$。你的任务是计算有多少对整数 $\langle A, B \rangle$ 满足 $1 \leq A, B \leq (A \oplus B) \leq N$，且 $(A \oplus B) \notin S$。 例如，令 $N = 10$，$S_{1..4} = \{4, 6, 7, 10\}$。共有 6 对 $\langle A, B \rangle$ 满足条件。 - $\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$ 注意，在此例中像 $\langle 2, 4 \rangle$ 这样的对不满足条件，因为 $(2 \oplus 4) = 6$ 而 $6 \in S$。另一对如 $\langle 5, 1 \rangle$ 也不满足条件，因为它违反了 $A, B \leq (A \oplus B)$ 的要求。

输入第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq 10^6$；$1 \leq M \leq 100\,000$），分别表示给定的 $N$ 和整数集合 $S_{1..M}$ 的大小。下一行包含 $M$ 个整数 $S_i$（$1 \leq S_i \leq 10^6$），表示整数集合 $S_{1..M}$。

输出一行一个整数，表示满足 $1 \leq A, B \leq (A \oplus B) \leq N$ 且 $(A \oplus B) \notin S_{1..M}$ 的 $\langle A, B \rangle$ 的对数。

#### 样例 #1 解释 此为题目描述中的示例。 #### 样例 #2 解释 共有 10 对 $\langle A, B \rangle$ 满足条件。 - $\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$ 翻译由 DeepSeek 完成