题目大意
有 (m) 个互不相同的非负整数 (a_1,a_2,dots,a_n) , 若 (a_i land a_j = 0) ，则在 (i) 和 (j) 之间连一条无向边，问能形成多少个连通块。
其中 (1 leq n leq 22) ， (1 leq m leq 2^n) ， (0 leq a_i leq 2^n - 1) 。
题解
考虑到对 (a_i) 每一位取反得到 (a_i') ，我们设 (a_i') 为 (1) 的二进制位组成的集合为 (T) , 设 (a_j) 为 (1) 的二进制位组成的集合为 (S) 。
若 (a_i land a_j = 0) ，则 (T in S) 。
我们用 (vis(a_i)) 来记录 (a_i) 是否被搜到过。
所以我们可以从 (1) 到 (n) 枚举 (a_i) ，若 (a_i) 未被搜到，则证明有一个新的连通块，首先让答案 (+1)。
然后进行一次 BFS ，枚举 (a_i) 的对应子集所对应的 (a_j) ，若 (a_j) 未被搜到，则加入队尾并修改 (vis(a_j)) 的值。（不会枚举子集的见底)
然后一直取出队头，重复这个过程。
（为什么不用 DFS ? 因为听说会爆栈，所以用 BFS 来做。 ）
然而，众所周知，这样枚举子集的时间复杂度是 (O(3^n))（证明见底） ，已经T飞了。所以我们不能这样做。
我们先将枚举到的未被搜到 (a_i) 取反得到 (a_i') 加入队列，然后进行 BFS 。
对于每一个队头 (cur) ，如果该队头是 (m) 个数之一，那么就对其取反得到 (cur') ，插入队尾并修改 (vis(cur')) 的值。
然后对于每个 (cur) ，先枚举 (2^0,2^1,2^2,dots,2^{n-1}) ，若 (cur - 2^k) 未被搜索到，则将其插入队尾并修改 (vis(cur - 2^k)) 的值。
为什么出现为 (m) 个数之一的 (cur) , 要对 (cur) 和 (cur') 都进行 BFS ？因为 (cur) 即可能作为搜到的可以连边的数，也可以作为继续减 (2^k) 以搜索子集的数。
显然时间复杂度为 (O(n2^n)) ，比上面的优秀很多。
看不懂上面解释的话还是看代码吧，自己模拟一下应该就可以理解。
#include <cstdio>
#define MAX_M ((1 << 22) + 5)
int n, m;
int a[MAX_M];
bool b[MAX_M], vis[MAX_M];
int q[MAX_M], l, r;
int ans;
int Read()
{
int res = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res;
}
int main()
{
n = Read();
m = Read();
for (int i = 1; i <= m; ++i)
{
a[i] = Read();
b[a[i]] = 1;
}
int cur;
const int lim = (1 << n) - 1;
for (int i = 1; i <= m; ++i)
{
if (vis[a[i]]) continue;
++ans;
l = r = 1;
q[l] = lim ^ a[i];
vis[a[i]] = vis[q[l]] = 1;
while (l <= r)
{
if (b[q[l]])
{
cur = lim ^ q[l];
if (!vis[cur])
{
q[++r] = cur;
vis[cur] = 1;
}
}
cur = q[l++];
for (int j = 1; j <= lim; j <<= 1)
{
if (!(cur & j) || vis[cur - j]) continue;
vis[cur - j] = 1;
q[++r] = cur - j;
}
}
}
printf("%d", ans);
return 0;
}
枚举子集：
for (int T = S; T; T = T - 1 & S)
不解释，模拟一下就懂了。
时间复杂度证明：
考虑一个大小为 (2^n) 的集合 (S) 。
(S) 的包含 (0) 个元素的子集有 (C_n^0) 个，每个子集有 (2^0) 个子集。
(S) 的包含 (1) 个元素的子集有 (C_n^1) 个，每个子集有 (2^1) 个子集。
拓展得， (S) 的包含 (m) 个元素的子集有 (C_n^m) 个，每个子集有 (2^m) 个子集。
所以总枚举数量为 (sumlimits_{i=0}^{n} 2^iC_n^i = sumlimits_{i=0}^{n} 2^i imes 1^{n-i} imes C_n^i) 。
根据二项式定理的得到上式 (= (2+1)^n = 3^n) 。
所以时间复杂度为 (O(3^n)) 。