CF1221G Graph And Number（容斥，搜索，FMT）

至今觉得这场 edu 的 G 比 EF 都要简单……

不知道为什么出题人要把 \(m=0\) 放进去，先特判掉。

要求至少一个 \(0\)，至少一个 \(1\)，至少一个 \(2\)，容斥一波，变成总方案数-没有 \(0\)-没有 \(1\)-没有 \(2\)+没有 \(01\)+没有 \(02\)+没有 \(12\)+没有 \(012\)。

没有 \(0\) 和没有 \(2\) 比较难搞，放到最后讨论。

没有 \(1\)，考虑一个联通块，这个联通块所有数都一样，方案数是 \(2^{cnt}\)，其中 \(cnt\) 是联通块个数。

没有 \(01\)，也就是只有 \(2\)，如果一个联通块中没有边（单独一个点），那么当然可以随便放，否则这个联通块所有数都是 \(1\)。方案数 \(2^{cnt2}\)，其中 \(cnt2\) 是单独一个点的联通块个数。

没有 \(02\)，也就是只有 \(1\)，等价于将这个图黑白染色的方案数。如果可以黑白染色，那么方案数是 \(2^{cnt}\)，否则是 \(0\)。

没有 \(12\)，和没有 \(01\) 一样。方案数是 \(2^{cnt2}\)。

没有 \(012\)，因为 \(m\ne 0\)，显然不可能。方案数为 \(0\)。

接下来就考虑没有 \(0\) 的方案数（没有 \(2\) 是一样的）。

这个数据范围很明显是让我们折半搜索。我们不妨先搜后半部分。

对于每个合法的后半部分（即没有两个是 \(0\) 的点相邻），前半部分有哪些点不能是 \(0\) 我们是知道的。

转变一下，变成当前半部分选取的 \(0\) 点集合为 \(S\) 时，后半部分有多少种方案 \(val_S\)。（我是这么写的）

满足条件的 \(S\) 就是不能选的点的补集的子集。

实际上，在补集的 \(val\) 加个 \(1\)，搜完后再做高维后缀和就能得到真的 \(val_S\)。应该不难理解。

然后再搜前半部分，对每个合法方案都加上它的 \(val\) 就行了。

时间复杂度，如果前半部分有 \(T\) 个点，复杂度是 \(O(2^TT+2^{n-T})\)。

由于我比较懒，我就取了 \(T=\frac{n}{2}\)。实际上要是 \(T\) 控制得够好，应该可以跑过 \(n=50\)。（取 \(T=23\)，大概是 3e8，3.5s+CF 神机应该没问题）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=1048576;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int n,m,cnt,cnt2,bar,lim;

ll e[40],ans,val[maxn];

bool ind[40],vis[40],col[40],flag=true;

void dfs(int u){

	vis[u]=true;

	FOR(v,0,n-1) if((e[u]>>v)&1){

		if(!vis[v]) col[v]=col[u]^1,dfs(v);

		else{

			if(col[v]!=(col[u]^1)) flag=false;

		}

	}

}

void dfs1(int dep,ll st,ll used){

	if(dep==bar) return void(val[(~st)&(lim-1)]++);

	dfs1(dep-1,st,used);

	if(!((st>>dep)&1)) dfs1(dep-1,st|e[dep],used|1<<dep);

}

void dfs2(int dep,ll st,ll used){

	if(dep==bar+1) return void(ans-=2*val[used&(lim-1)]);

	dfs2(dep+1,st,used);

	if(!((st>>dep)&1)) dfs2(dep+1,st|e[dep],used|1<<dep);

}

int main(){

	n=read();m=read();

	if(!m) return puts("0"),0;

	FOR(i,0,n-1) ind[i]=true;

	FOR(i,1,m){

		int u=read()-1,v=read()-1;

		e[u]|=1ll<<v;e[v]|=1ll<<u;

		ind[u]=ind[v]=false;

	}

	FOR(i,0,n-1) if(ind[i]) cnt2++;

	FOR(i,0,n-1) if(!vis[i]) cnt++,dfs(i);

	ans=(1ll<<n)-(1ll<<cnt)+(1ll<<cnt2)+(1ll<<cnt2)+(flag?1ll<<cnt:0);

	bar=(n-1)/2;lim=1<<(bar+1);

	dfs1(n-1,0,0);

	for(int i=1;i<lim;i<<=1)

		for(int j=0;j<lim;j+=i<<1)

			FOR(k,0,i-1) val[j+k]+=val[i+j+k];

	dfs2(0,0,0);

	printf("%lld\n",ans);

}