AND Graph

题意翻译

给定一个 $m$ 个整数的集合，每个整数在 $0$ 到 $2^n-1$ 之间，以每一个整数作为顶点建无向图，当两个点 $x$ 和 $y$ 做与运算值为 $0$ 时，则认为 $x$ 和 $y$ 是连通的，即 $x$ 和 $y$ 之间有一条无向边。请求出图中连通块的个数。 **【输入格式】** 第一行输入两个整数 $n$ 和 $m$（$0 \leq n\leq22$，$1 \leq m\leq2^n$）。 第二行输入 $m$ 个整数，即集合里的元素。 **【输出格式】** 一个整数，表示图中连通块的个数。

题目描述

You are given a set of size $ m $ with integer elements between $ 0 $ and $ 2^{n}-1 $ inclusive. Let's build an undirected graph on these integers in the following way: connect two integers $ x $ and $ y $ with an edge if and only if $ x \& y = 0 $ . Here $ \& $ is the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Count the number of connected components in that graph.

输入输出格式

输入格式

In the first line of input there are two integers $ n $ and $ m $ ( $ 0 \le n \le 22 $ , $ 1 \le m \le 2^{n} $ ). In the second line there are $ m $ integers $ a_1, a_2, \ldots, a_m $ ( $ 0 \le a_{i} < 2^{n} $ ) — the elements of the set. All $ a_{i} $ are distinct.

输出格式

Print the number of connected components.

输入输出样例

输入样例 #1

2 3
1 2 3

输出样例 #1

2

输入样例 #2

5 5
5 19 10 20 12

输出样例 #2

2

说明

Graph from first sample:  Graph from second sample: 

题意翻译

给定一个 $m$ 个整数的集合，每个整数在 $0$ 到 $2^n-1$ 之间，以每一个整数作为顶点建无向图，当两个点 $x$ 和 $y$ 做与运算值为 $0$ 时，则认为 $x$ 和 $y$ 是连通的，即 $x$ 和 $y$ 之间有一条无向边。请求出图中连通块的个数。 **【输入格式】** 第一行输入两个整数 $n$ 和 $m$（$0 \leq n\leq22$，$1 \leq m\leq2^n$）。 第二行输入 $m$ 个整数，即集合里的元素。 **【输出格式】** 一个整数，表示图中连通块的个数。