← 返回题目

题库练习 AND Graph

← 上一题下一题 →

A11830 | $AND Graph$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

5 5
5 19 10 20 12

输出 #2

C++ 编辑器

输入

输出