CF986C AND Graph

出题人纯nt要用bitset存bool数组来卡空间也真是没谁了

这题的思路其实有点像高维前缀和，考虑对于某个数\(x\)，我们知道\(y=(2^n-1)\oplus x\)与\(x\)的与一定为\(0\)，且\(y\)的所有子集也满足与\(x\)后为\(0\)

考虑怎么处理这种子集关系，我们借鉴于高维前缀和，每次把某个数\(y\)的某一位拿掉一个\(1\)后得到\(y'\)，建边\(y\to y'\)，这样可以在\(O(2^n\times n)\)的边数范围内得到一张代表了子集关系的图

因此这题的做法就很简单了，我们除了原图\(G\)之外再维护一个构造方式如上所述的图\(G'\)

• 对于每个\(a_i\)，将\(G\)中的\(a_i\)向\(G'\)中的\((2^n-1)\oplus a_i\)连边
• 对于每个\(x\in G'\)，除了连上述表示子集关系的边外，再向\(G\)中的\(x\)连边

最后直接DFS跑一下图中的连通块数量即可，总复杂度\(O(2^n\times n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=22;
int n,m,tot,a[(1<<N)+5],ans;
bitset <(1<<N)+5> c; bitset <(1<<N+1)+5> vis;
inline void DFS(int now)
{
	vis[now]=1; if (now<tot)
	{
		if (c[now]&&!vis[((tot-1)^now)+tot]) DFS(((tot-1)^now)+tot);
	} else
	{
		if (!vis[now-tot]) DFS(now-tot);
		auto lowbit=[&](int x)
		{
			return x&(-x);
		};
		for (int x=now-tot;x;x-=lowbit(x))
		if (!vis[((now-tot)-lowbit(x))+tot]) DFS(((now-tot)-lowbit(x))+tot);
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),tot=1<<n,i=0;i<m;++i) scanf("%d",&a[i]),c[a[i]]=1;
	for (i=0;i<m;++i) if (!vis[a[i]]) ++ans,DFS(a[i]);
	return printf("%d",ans),0;
}