{"problem":{"name":"C. AND Graph","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF986C"},"statements":[{"statement_type":"Markdown","content":"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 \\&amp; y = 0$. Here $\\&amp;$ is the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Count the number of connected components in that graph.\n\n## Input\n\nIn the first line of input there are two integers $n$ and $m$ ($0 \\le n \\le 22$, $1 \\le m \\le 2^{n}$).\n\nIn the second line there are $m$ integers $a_1, a_2, \\ldots, a_m$ ($0 \\le a_{i} &lt; 2^{n}$) — the elements of the set. All $a_{i}$ are distinct.\n\n## Output\n\nPrint the number of connected components.\n\n[samples]\n\n## Note\n\nGraph from first sample:\n\n![image](https://espresso.codeforces.com/2ae9959ec95b178e60e27e28f5d62c1099bb9ef1.png)\n\nGraph from second sample:\n\n![image](https://espresso.codeforces.com/9f9eee8f2409bbd78cce726875915c405af8a07e.png)","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你一个大小为 $m$ 的集合，其中的整数元素在 $0$ 到 $2^n -1$ 之间（包含端点）。我们按照如下方式在这些整数上构建一个无向图：当且仅当 $x & y = 0$ 时，在整数 $x$ 和 $y$ 之间连一条边。这里 $&$ 表示按位与运算。请计算该图中连通分量的数量。\n\n输入的第一行包含两个整数 $n$ 和 $m$（$0 lt.eq n lt.eq 22$，$1 lt.eq m lt.eq 2^n$）。\n\n第二行包含 $m$ 个整数 $a_1, a_2, dots.h, a_m$（$0 lt.eq a_i < 2^n$）——集合的元素。所有 $a_i$ 互不相同。\n\n请输出连通分量的数量。\n\n第一个样例的图：\n\n第二个样例的图：\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $m$（$0 lt.eq n lt.eq 22$，$1 lt.eq m lt.eq 2^n$）。第二行包含 $m$ 个整数 $a_1, a_2, dots.h, a_m$（$0 lt.eq a_i < 2^n$）——集合的元素。所有 $a_i$ 互不相同。\n\n## Output\n\n请输出连通分量的数量。\n\n[samples]\n\n## Note\n\n第一个样例的图：\n\n第二个样例的图：","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ S \\subseteq \\{0, 1, \\dots, 2^n - 1\\} $ with $ |S| = m $, and define an undirected graph $ G = (S, E) $ where:\n\n$$\nE = \\{ \\{x, y\\} \\mid x, y \\in S, \\; x \\ne y, \\; x \\mathbin{\\&} y = 0 \\}\n$$\n\nCount the number of connected components of $ G $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF986C","tags":["bitmasks","dfs and similar","dsu","graphs"],"sample_group":[["2 3\n1 2 3","2"],["5 5\n5 19 10 20 12","2"]],"created_at":"2026-03-03 11:00:39"}}