题解 CF1221G 【Graph And Numbers】

在我的博客园看效果更佳：点这里

至今觉得这场 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);
}