← 返回题目列表

Codeforces · 986/C

C. 与图

中文机器翻译题面 查看原题

给定一个大小为 $$$m$$$ 的集合,其中整数元素介于 $$$0$$$ 和 $$$2^{n}-1$$$ 之间(含)。让我们按照以下方式在这些整数上构建一个无向图:当且仅当 $$$x \& y = 0$$$ 时,用边连接两个整数 $$$x$$$ 和 $$$y$$$。这里$$$\&$$$是按位与运算。计算该图中连接组件的数量。

输入

输入的第一行有两个整数 $$$n$$$ 和 $$$m$$$ ($$$0 \le n \le 22$$$, $$$1 \le m \le 2^{n}$$$)。

第二行有 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$ ($$$0 \le a_{i} < 2^{n}$$$) - 集合的元素。所有 $$$a_{i}$$$ 都是不同的。

输出

打印连接组件的数量。

示例

输入 #1

2 3
1 2 3

输出 #1

2

输入 #2

5 5
5 19 10 20 12

输出 #2

2

注意

第一个样本的图表:

第二个样本的图表: