自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:57:15，当前版本为作者最后更新于2024-06-17 16:15:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

二分图的运用。

如果原图是二分图，那么考虑将他进行黑白二染色，并且把条件改为“两端颜色不同才能翻转”。

那么发现，一次操作相当于把一个黑点移动了一条边的位置，且末状态是所有黑点变为白点，所有白点变为黑点。

显然如果黑点有 $b$ 个，白点有 $w$ 个，最终方案是 $\dbinom{b+w}{b}$。

如果不是二分图，考虑求出它的一个子图是二分图，那么非二分图边在同色的时候翻转。

那么这种边没操作一次会使得 $b \pm 2$，奇偶性不变。因此只要末状态和初状态黑点的奇偶性相同，就可以到达。方案是 $2^{b+w-1}$。

染色即可。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=200000+10,MOD=1e9+7;
int n,m,ans=1,frac[MAXN],inv[MAXN],c[MAXN],col[MAXN],vis[MAXN],pw[MAXN];
vector<int> G[MAXN];
int qpow(int base,int p) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;	
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
int C(int u,int d) {return frac[d]*inv[u]%MOD*inv[d-u]%MOD;}
int check(int u) {
	int flg=0;
	vis[u]=1,c[u]^=col[u];
	for(auto v:G[u]) {
		if(vis[v]==0) col[v]=col[u]^1,flg|=check(v);
		if(col[v]!=col[u]^1) flg=1;
	}
	return flg;
}
pair<int,int> query(int u) {
	vis[u]=2;
	pair<int,int> ans={1,c[u]};
	for(auto v:G[u]) if(vis[v]==1) {
		auto pr=query(v);
		ans.first+=pr.first,ans.second+=pr.second;
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,pw[0]=1,frac[0]=1;
	ffor(i,1,n) cin>>c[i],pw[i]=pw[i-1]*2%MOD,frac[i]=frac[i-1]*i%MOD;
	inv[n]=qpow(frac[n],MOD-2);
	roff(i,n-1,0) inv[i]=inv[i+1]*(i+1)%MOD;
	ffor(i,1,m) {int u,v;cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
	ffor(i,1,n) if(!vis[i]) {
		int flg=check(i);
		auto pr=query(i);
		if(flg==1) ans=ans*pw[pr.first-1]%MOD;
		else ans=ans*C(pr.second,pr.first)%MOD;
	}
	cout<<ans;
	return 0;
}