题解：P10367 [PA2024] Żarówki

· · 题解

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;
}