题目
题目描述
小C和小G经常在一起研究搏弈论问题，有一天他们想到了这样一个游戏．
有一个 $n$个点 $m$ 条边的无向图，初始时每个节点有一个颜色，要么是黑色，要么是白色．现在他们对于每条边做出一次抉择：要么将这条边连接的两个节点都反色（黑变白，白变黑），要么不作处理．他们想把所有节点都变为白色，他们想知道在 $2^m$ 种决策中，有多少种方案能达成这个目标．
小G认为这个问题太水了，于是他还想知道，对于第$ i$ 个点，在删去这个点及与它相连的边后，新的答案是多少．
由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模后的结果．
输入格式
第一行一个整数 $T$ ，表示数据组数．
每组数据第一行两个整数 $n, m$ ，表示点数和边数.
接下来 $m$m 行，每行两个整数 $u, v$ ，描述无向图的一条边．
接下来一行一个长度为 $n$ 的 0/1 串，如果第 $i$ 个字符为 $0$ 表示第 $i$ 个点为白色，否则为黑色．
输出格式
每组数据输出一行 $n + 1$ 个整数，第一个整数表示不删去任何点时的答案．接下来 $n$ 个整数，第 $i$ 个表示删去第 $i$ 个点时的答案．
样例
样例输入
2
5 5
1 2
2 3
3 4
2 4
3 5
00000
5 4
1 2
2 3
2 4
2 5
11111
样例输出
2 2 1 1 1 2
0 1 0 1 1 1
样例解释
第一组数据，在不删掉任何点时，有两种方案：要么对所有的边都不做操作；要么对 $(2, 3), (3, 4), (2, 4)$ 做操作．
在删掉 $2$ 号点或 $3$ 号点或 $4$ 号点时，唯一的方案是对所有边都不做操作．注意图可能不连通．
数据范围与提示
对于所有数据，有 $1 \le T \le 5, 1 \le n, m \le 10^5, 1 \le u, v \le n$ ，没有重边和自环．
题解
虽然$LOJ$的题面很好看但是没有部分的数据范围emmm
对于较小的$n,m$，发现题目要求的就是一个异或方程组的解的方案数
设$N$为方程组中的自由元的个数，则答案就是$2^N$
所以可以高斯消元异或方程组，能得$60$分
发现可以对一个连通块单独处理，如果这个连通块的黑点个数为奇数，那么怎么也不可能让这个连通块变成全白
对于一个$M$个点的连通块来说，如果确定了其中$M-1$个点的颜色，剩下的那个点的颜色一定确定了，所以一个连通块的自由元为$M-1$
所以答案为$2^{m-n-t}$，$t$为连通块个数
然后就是一大堆特判了……实在不想写OAO
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<bitset>
# include<algorithm>
using namespace std;
const int MAX=1e5+5,mod=1e9+7;
struct p{
int x,y;
}c[MAX<<1];
int T,n,m,ans,Top,cnt,num,tot,A;
int h[MAX],qwq[MAX],val[MAX],low[MAX],dfn[MAX],col[MAX],du[MAX],qaq[MAX];
char a[MAX];
bool use[MAX],oao[MAX],ouo[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void Tarjan(int x,int F)
{
low[x]=dfn[x]=++cnt,col[x]=F,val[x]=(a[x]=='1');
if(x==F&&!h[x]) return void(ouo[x]=1);
for(int i=h[x];i;i=c[i].x)
if(!dfn[c[i].y])
{
Tarjan(c[i].y,F),low[x]=min(low[x],low[c[i].y]),val[x]+=val[c[i].y];
if(low[c[i].y]>=dfn[x])
{
++qaq[x],oao[x]|=(val[c[i].y]&1);
if(x!=F||qaq[x]>1) use[x]=1;
}
}
else low[x]=min(low[x],dfn[c[i].y]);
++qaq[x];
if(x==F) --qaq[x];
}
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num,++du[x];
c[++num]=(p){h[y],x},h[y]=num,++du[y];
}
int main()
{
T=read(),qwq[0]=1;
for(int i=1;i<MAX;++i)
qwq[i]=(qwq[i-1]<<1ll)%mod;
while(T--)
{
n=read(),m=read(),num=cnt=tot=A=0;
memset(h,0,sizeof(h));
memset(du,0,sizeof(du));
memset(val,0,sizeof(val));
memset(col,0,sizeof(col));
memset(oao,0,sizeof(oao));
memset(ouo,0,sizeof(ouo));
memset(qaq,0,sizeof(qaq));
memset(use,0,sizeof(use));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(use,0,sizeof(use));
for(int i=1;i<=m;++i)
add(read(),read());
scanf("%s",a+1);
for(int i=1;i<=n;++i)
if(!dfn[i]) Tarjan(i,i),++tot,A+=(val[i]&1);
for(int i=1;i<=n;++i)
oao[i]|=(val[col[i]]-(a[i]=='1')&1);
if(A) printf("0 ");
else printf("%d ",qwq[m-n+tot]);
for(int i=1,cnt;i<=n;++i)
if(!use[i])
{
if(a[i]=='0')
{
if(A) printf("0 ");
else printf("%d ",qwq[m-du[i]-n+1+tot-ouo[i]]);
}
else if(A+((val[col[i]]-(a[i]=='1')&1)?1:-1)) printf("0 ");
else printf("%d ",qwq[m-du[i]-n+1+tot]);
}
else
{
if(oao[i]) printf("0 ");
else if(A-(val[col[i]]&1)) printf("0 ");
else printf("%d ",qwq[m-du[i]-n+tot+qaq[i]]);
}
printf("\n");
}
return 0;
}
