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?'
':' ');
}
}
return 0;
}