LOJ2524「HAOI2018」反色游戏

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;
}
上一篇:图书馆用文本文件booklist.txt记录图书的书目,其中包括book1,book2,.....,book10.现在又要采购一批新书,编写程序将新的书目添加到目录中。


下一篇:P4494 [HAOI2018]反色游戏