AND Graph

4000ms

262144K

Description:

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. Count the number of connected components in that graph.

Input:

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.

Output:

Print the number of connected components.

Sample Input:

2 3
1 2 3

Sample Output:

Sample Input:

5 5
5 19 10 20 12

Sample Output:

Note:

Graph from first sample:

$\text{[math]}$

Graph from second sample:

$\text{[math]}$

Informação

Provedor Codeforces

Código CF986C