bzoj 5303: [Haoi2018]反色游戏

Description

Solution

对于一个有偶数个黑点的连通块,只需要任意两两配对,并把配对点上的任一条路径取反,就可以变成全白了

如果存在奇数个黑点的连通块显然无解,判掉就可以了

如果有解,解的数量肯定是一样的(白点被取反偶数次,黑点奇数次)

一共有 \(2^{m}\) 种染色方案,有 \(2^{n-1}\) 把点染成偶数个白色的方案,因为每一种方案可以产生的解是一样的,那么就有 \(2^{m-n+1}\) 种解

所以对于每一个连通块产生的贡献就是 \(2^{m-n+1}\),如果有 \(c\) 个连通块,答案就是 \(2^{m-n+c}\) 种方案

删掉一个点之后,就只需要判断是否存在新产生的连通块黑点个数是偶数,并且统计一下连通块的个数就可以知道答案了

#include<bits/stdc++.h>

using namespace std;

template<class T>void gi(T &x){

	int f;char c;

	for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

	for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;

}

const int N=1e5+10,mod=1e9+7;

int n,m,head[N],nxt[N*2],to[N*2],num=0,ID=0,in[N];

inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}

int dfn[N],low[N],DFN=0,w[N],d[N],f[N],bin[N*2],b[N],g[N];char s[N];

inline void tarjan(int x){

	dfn[x]=low[x]=++DFN;b[x]=ID;w[x]=s[x]-'0';

	for(int i=head[x];i;i=nxt[i]){

		int u=to[i];

		if(!dfn[u]){

			tarjan(u);

			low[x]=min(low[x],low[u]);w[x]+=w[u];

			if(low[u]>=dfn[x])d[x]|=(w[u]&1),f[x]++,g[x]+=w[u];

		}

		else low[x]=min(low[x],dfn[u]);

	}

	if(x==ID)f[x]--;

}

inline void work(){

	int x,y;

	cin>>n>>m;

	for(int i=1;i<=m;i++){

		gi(x);gi(y);in[x]++;in[y]++;

		link(x,y);link(y,x);

	}

	scanf("%s",s+1);

	int ans=m-n,c=0;

	for(int i=1;i<=n;i++)

		if(!dfn[i])ID=i,tarjan(i),ans++,c+=(w[i]&1);

   printf("%d",c?0:bin[ans]);

	for(int i=1;i<=n;i++){

		if(d[i])printf(" 0");

		else if(c-(w[b[i]]&1))printf(" 0");

		else if((w[b[i]]-(s[i]=='1')-g[i])&1)printf(" 0");

		else printf(" %d",bin[ans-in[i]+1+f[i]]);

	}

}

inline void Clear(){

	DFN=num=0;

	for(int i=0;i<N;i++)head[i]=dfn[i]=low[i]=f[i]=d[i]=in[i]=g[i]=0;

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  int T;cin>>T;

  bin[0]=1;for(int i=1;i<200005;i++)bin[i]=bin[i-1]*2%mod;

  while(T--)Clear(),work(),puts("");

  return 0;

}

巴特西

bzoj 5303: [Haoi2018]反色游戏

Description

Solution

最新文章

热门文章