AT_pakencamp_2023_day1_k Or Set

给定一个正整数 $M$ 和一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots ,A_N)$。这里保证 $0 \leq A_i \leq 2^M-1$。另外，存在一个最初为 $X=0$ 的整数 $X$。 你可以将 $A$ 的元素任意重新排列，然后按 $i=1,2,\ldots,N$ 的顺序依次进行如下操作： - 如果 $X\ \mathrm{or}\ A_i \neq 2^M-1$，则将 $X$ 替换为 $X\ \mathrm{or}\ A_i$。 请你计算，作为操作结束后 $X$ 可能取到的不同值的个数。 这里的 $\mathrm{or}$ 指按位或运算。对于整数 $a, b$，按位或 $a\ \mathrm{or}\ b$ 的定义如下：当 $a, b$ 的二进制表示下第 $2^k \ (0 \leq k)$ 位中只要有一个为 $1$，则 $a\ \mathrm{or}\ b$ 的该位也为 $1$，否则为 $0$。 例如，$12\ \mathrm{or}\ 6=14$。二进制形式为 $1100\ \mathrm{or}\ 0110=1110$。

输入按照以下格式从标准输入读入。 > $N$   $M$   $A_1$   $A_2$   $\ldots$   $A_N$

请输出最终可能的 $X$ 的取值个数。

### 样例解释 1 最终 $X$ 可能的值有 $3$ 和 $6$，共 $2$ 种可能。 例如，若 $A=(4,3,6)$，操作过程如下： - $X \ \mathrm{or}\ A_1 = 0 \ \mathrm{or}\ 4 = 4 \neq 2^3-1$，所以将 $X$ 更新为 $4$。 - $X \ \mathrm{or}\ A_2 = 4 \ \mathrm{or}\ 3 = 7 = 2^3-1$，所以不进行操作。 - $X \ \mathrm{or}\ A_3 = 4 \ \mathrm{or}\ 6 = 6 \neq 2^3-1$，所以将 $X$ 更新为 $6$。 因此，最终 $X$ 的值为 $6$。 ### 数据范围 - $1 \leq N \leq 2\times 10^5$ - $1 \le M \le 30$ - $0 \le A_i < 2^M$ - 输入均为整数。 由 ChatGPT 5 翻译