题解 CF1221G 【Graph And Numbers】
AThousandSuns
2019-09-22 12:35:32
在我的博客园看效果更佳：[点这里](https://www.cnblogs.com/1000Suns/p/11566940.html)
至今觉得这场 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 神机应该没问题）
```cpp
#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);
}
```