LOJ2524「HAOI2018」反色游戏

题面：LOJ

解析

首先考虑一个联通块怎么做。观察到若连通块为一棵树，如果黑点个数为偶数，则有且仅有一组解；反之无解。奇数的情况不难证明，因为一次反色改变黑点的个数总是偶数。现在考虑偶数，用归纳法逐层构造不难得到一组解，考虑如何证明解的唯一性。不难发现，对于当前正在构造的一颗子树，最多只能上传一个黑点（因为多余的只能通过子树内部的反色来去掉），而且这个上传的黑点的位置一定是当前子树的根节点。再次考虑归纳法，现在假设子树根节点的儿子的子树部分方案唯一，而儿子的颜色仅与子树内的黑点个数有关，现在儿子颜色确定，那么唯一的方案就是将根节点到所有黑色儿子的边反色，这样我们就证明了对于更大的子树，方案依然具有唯一性，那么这个结论得证。

现在考虑这个联通块不为树的情况。考虑\(dfs\)树，那么剩下的每一条返祖边有两种选择，但是我们发现，对于每一条返祖边，将返祖边对应的路径取值异或返祖边的取值，就能消除返祖边的影响，也就是说，这个联通块和树其实是一样的，那么方案数就是\(2^{m-n+1}\)。

现在考虑有\(c\)个联通块的方案数，那么就是\(2^{m-n+c}\)。

那么删掉一个点\(i\)如何做呢？大致分割点和非割点讨论一下就行了。

代码

#include<cstdio>
#include<cstring>
#define N 100005

using namespace std;

const int P=1e9+7;

inline int In(){
    char c=getchar(); int x=0,ft=1;
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ft=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
    return x*ft;
}

inline int power(int x,int k){
    int s=1,t=x;
    for(;k;k>>=1,t=1ll*t*t%P)
    if(k&1) s=1ll*s*t%P;
    return s;
}

inline int min(int a,int b){
    return a<b?a:b;
}

int n,m,ans,e_tot,f_cnt,f_cid,c_cnt,dfs_clock;
int h[N],opt[N],deg[N],dfn[N],low[N],id[N],uc[N],sz[N];
char str[N]; bool iscut[N],fr[N],vis[N];
struct E{ int to,nex; }e[N<<1];

void Init(){
    e_tot=f_cnt=c_cnt=dfs_clock=0;
    memset(h,0,sizeof(h));
    memset(deg,0,sizeof(deg));
    memset(dfn,0,sizeof(dfn));
    memset(uc,0,sizeof(uc));
    memset(sz,0,sizeof(sz));
    memset(iscut,0,sizeof(iscut));
    memset(fr,0,sizeof(fr));
    memset(vis,0,sizeof(vis));
}


inline void add(int u,int v){
    e[++e_tot]=(E){v,h[u]}; h[u]=e_tot;
}

void dfs(int u,int pre){
    dfn[u]=low[u]=++dfs_clock;
    sz[u]=opt[u]; id[u]=c_cnt;
    int child=0;
    for(int i=h[u],v;i;i=e[i].nex){
        if((v=e[i].to)==pre) continue;
        if(!dfn[v]){
            dfs(v,u); ++child; sz[u]+=sz[v];
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                iscut[u]=1;
                ++uc[u]; fr[u]|=(sz[v]&1);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(pre==-1){
        if(child==1) iscut[u]=0;
        else --uc[u];
    }
}

int main(){
    int T=In();
    while(T--){
        Init(); n=In(); m=In();
        for(int i=1,u,v;i<=m;++i){
            u=In(); v=In();
            add(u,v); ++deg[u];
            add(v,u); ++deg[v];
        }
        scanf("%s",str+1);
        for(int i=1;i<=n;++i) opt[i]=(str[i]=='1');
        for(int i=1;i<=n;++i) if(!dfn[i]){
            ++c_cnt; dfs(i,-1);
            if(sz[i]&1){ ++f_cnt; f_cid=c_cnt; }
        }
        if(!f_cnt) ans=power(2,m-n+c_cnt); else ans=0;
        printf("%d ",ans);
        for(int i=1;i<=n;++i){
            if(deg[i]==0){
                if(opt[i]==0) printf("%d",ans);
                else{
                    if(f_cnt>1) printf("%d",0);
                    else printf("%d",power(2,m-n+c_cnt));
                }
            }
            else if(iscut[i]==0){
                if(opt[i]==0){
                    if(ans==0) printf("%d",0);
                    else printf("%d",power(2,m-deg[i]-n+1+c_cnt));
                }
                else{
                    if(f_cnt>1) printf("%d",0);
                    else if(f_cnt==1){
                        if(id[i]!=f_cid) printf("%d",0);
                        else printf("%d",power(2,m-deg[i]-n+1+c_cnt));
                    }
                    else printf("%d",0);
                }
            }
            else{
                if(fr[i]==1) printf("%d",0);
                else{
                    if(opt[i]==0){
                        if(f_cnt>1) printf("%d",0);
                        else if(f_cnt==1){
                            if(id[i]!=f_cid) printf("%d",0);
                            else printf("%d",0);
                        }
                        else printf("%d",power(2,m-deg[i]-n+1+c_cnt+uc[i]));
                    }
                    else{
                        if(f_cnt>1) printf("%d",0);
                        else if(f_cnt==1){
                            if(id[i]!=f_cid) printf("%d",0);
                            else printf("%d",power(2,m-deg[i]-n+1+c_cnt+uc[i]));
                        }
                        else printf("%d",0);
                    }
                }
            }
            printf("%c",i==n?'\n':' ');
        }
    }
    return 0;
}