题意简述

给定 $m$ 个 $[0, 2^{22})$ 内的整数，每个整数可以访问与其按位与为 $0$ 的数（即 $a \& b = 0$）。从任意一个给定的数出发，可以不断跳转到与当前数按位与为 $0$ 的数。问最终能访问到多少个不同的数（包括初始给定的数）。

思路分析

核心转化

条件 $a \& b = 0$ 等价于 $b$ 是 $a$ 的补集的子集，即 $b \subseteq \sim a$（其中 $\sim a$ 表示按位取反，这里只考虑低 22 位）。
因此，若我们从 $a$ 出发，可以到达所有 $\sim a$ 的子集。

图论建模

我们想构造一张图，使得从 $a$ 出发能遍历到所有与它按位与为 $0$ 的数。

• 子集枚举图：对每个数 $x$，向所有只比 $x$ 少一个 1 的子集连有向边。这样从 $x$ 出发可以遍历 $x$ 的所有子集（按位 $1$ 逐个删除）。
• 取反边：为了从 $a$ 跳到 $\sim a$ 的子集，需要一条 $a \to \sim a$ 的边。

于是设计两层图：

• 层 A：表示原始的数。
• 层 B：表示补集空间，用于枚举子集。

连边规则：

1. $A(u) \to B(\sim u)$：进入补集空间。
2. $B(u) \to B(v)$，其中 $v$ 是 $u$ 去掉一个 1 得到（即 $v = u \oplus (1 << i)$ 且 $u$ 的第 $i$ 位为 1）：在补集空间中枚举子集。
3. $B(u) \to A(u)$：从补集空间回到原数。

这样，$A(u)$ 可以到达所有满足 $u \& v = 0$ 的 $A(v)$。因为：$A(u) \to B(\sim u) \xrightarrow{\text{枚举子集}} B(v) \to A(v)$，其中 $v \subseteq \sim u$，即 $u \& v = 0$。

算法实现

题目还规定：某些数不可作为起点（即初始不可访问），但可以通过其他数间接到达。
实际上我们关心的是：从所有给定的数出发，能访问到的数的总数。

可以将所有给定的数标记为“初始可访问”（但未被访问），然后对每个未被访问的给定数进行 DFS/BFS，标记所有能到达的数。由于图的总节点数为 $2 \times 2^{22} = 2^{23}$，可以用一个 bitset 来标记访问状态，空间可接受。

DFS 实现细节

代码中将 $[0, N)$ 视为 A 层（原数），$[N, 2N)$ 视为 B 层（补集空间，其中 $N = 2^{22}$）。

• dfs(u) 中：
  • 如果 $u < N$（A 层）：先跳到 B 层的补集 (MA ^ u) + N，其中 MA = N-1 是低 22 位全 1。
  • 如果 $u \ge N$（B 层）：先跳回 A 层（u - N），然后枚举所有去掉一个 1 的子集，继续 DFS。

这样一次 DFS 会标记所有与起点按位与为 0 的连通分量。

时间复杂度

每个节点只会被访问一次，总状态数 $2^{23} \approx 8\times 10^6$，DFS 内部枚举每一位的复杂度 $O(22)$，总复杂度 $O(22 \cdot 2^{23})$ 仍可接受，且代码中用 bitset 优化了存储与标记。

AC 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1 << 22;      // 2^22 = 4194304
const int MA = N - 1;       // 低 22 位全 1
int n, m, a[N + 5], ans;
bitset<(N << 1)> vis;       // 两层图，共 2N 个节点

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = 1;

    if (u < N) {
        // A 层：跳到 B 层的补集
        dfs((MA ^ u) + N);
    } else {
        // B 层：先跳回 A 层
        dfs(u - N);
        // 枚举去掉一个 1 的子集
        int x = u - N;
        for (int i = 0; i < 22; ++i) {
            if ((x >> i) & 1) {
                dfs(u - (1 << i));   // 注意 u 是 B 层编号，减去 (1<<i) 相当于在 B 层去掉一个 1
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);   // 这里 n 实际是 2^22? 原题 n 可能表示位数，但代码中未使用
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &a[i]);
        vis[a[i]] = 0;       // 标记 A 层的这些点为未访问（初始可访问）
    }
    // 注意：vis 初始所有位为 1？上面代码中 bitset 默认全 0，这里需要调整逻辑。
    // 原代码有：for(int i=0;i<N;++i) vis[i]=1; 但被注释掉了？实际正确做法是：
    // 将所有 A 层初始为未访问（即 vis[i]=0），给定的数可访问，其他数不可访问。
    // 但原代码逻辑是：vis[i]=1 表示已访问，先全部标记为 1，再把给定点标记为 0，
    // 然后对每个给定点，如果 vis[a[i]]==0 则 DFS。这样就能保证从给定点开始标记整个连通分量。
    // 这里需要修正 bitset 初始化。由于 bitset 默认全 0，应将所有点先置为 1。
    vis.set();               // 将所有位设为 1
    for (int i = 1; i <= m; ++i) {
        vis[a[i]] = 0;       // 给定点初始未访问
    }

    for (int i = 1; i <= m; ++i) {
        if (!vis[a[i]]) {
            ++ans;
            dfs(a[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}