#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int mod = 1e9 + 7; struct Mint { int val; Mint(ll x = 0): val((x % mod + mod) % mod) {;} Mint operator +(const Mint& x) { return Mint(val + x.val); } Mint operator -(const Mint& x) { return Mint(val - x.val); } Mint operator *(const Mint& x) { return Mint((ll)val * x.val); } Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); } Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); } Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); } Mint operator ^(const int& _b) const { Mint accum = 1, a = *this; int b = _b; while(b) { accum = (b & 1? accum * a : accum); a *= a; b >>= 1; } return accum; } Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); } Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); } }; namespace COMBI { const int nmax = 2e5 + 5; Mint fact[nmax], invfact[nmax]; void init(int n = nmax - 1) { fact[0] = 1; for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i; invfact[n] = Mint(1) / fact[n]; for(int i = n; i > 0; i--) invfact[i - 1] = invfact[i] * Mint(i); return; } Mint f(int n) { return fact[n]; } Mint invf(int n) { return invfact[n]; } Mint ncr(int n, int r) { return fact[n] * invfact[r] * invfact[n - r]; } } const int nmax = 2e5 + 5; int light[nmax]; int atrcol[nmax]; vector<int> g[nmax]; bool bipartit = 1; int cnt[2] = {0, 0}; void checkbip(int node, int trial) { if(atrcol[node] != 0) { if(atrcol[node] != trial) bipartit = 0; return; } cnt[0]++; if((light[node] ^ (trial - 1)) == 1) cnt[1]++; atrcol[node] = trial; for(auto x : g[node]) checkbip(x, 3 - trial); return; } signed main() { COMBI::init(); cin.tie(0) -> sync_with_stdio(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> light[i]; for(int x, y, i = 1; i <= m; i++) { cin >> x >> y; g[x].emplace_back(y); g[y].emplace_back(x); } Mint total = 1; for(int i = 1; i <= n; i++) { if(atrcol[i] == 0) { bipartit = 1; cnt[0] = cnt[1] = 0; checkbip(i, 1); //cerr << i << '\t' << cnt[0] << ' ' << cnt[1] << '\n'; if(bipartit == 0) total *= Mint(2) ^ (cnt[0] - 1); else total *= COMBI::ncr(cnt[0], cnt[1]); } } cout << total.val << '\n'; } /** Anul asta nu se da centroid -- Rugaciunile mele */
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int mod = 1e9 + 7; struct Mint { int val; Mint(ll x = 0): val((x % mod + mod) % mod) {;} Mint operator +(const Mint& x) { return Mint(val + x.val); } Mint operator -(const Mint& x) { return Mint(val - x.val); } Mint operator *(const Mint& x) { return Mint((ll)val * x.val); } Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); } Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); } Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); } Mint operator ^(const int& _b) const { Mint accum = 1, a = *this; int b = _b; while(b) { accum = (b & 1? accum * a : accum); a *= a; b >>= 1; } return accum; } Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); } Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); } }; namespace COMBI { const int nmax = 2e5 + 5; Mint fact[nmax], invfact[nmax]; void init(int n = nmax - 1) { fact[0] = 1; for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i; invfact[n] = Mint(1) / fact[n]; for(int i = n; i > 0; i--) invfact[i - 1] = invfact[i] * Mint(i); return; } Mint f(int n) { return fact[n]; } Mint invf(int n) { return invfact[n]; } Mint ncr(int n, int r) { return fact[n] * invfact[r] * invfact[n - r]; } } const int nmax = 2e5 + 5; int light[nmax]; int atrcol[nmax]; vector<int> g[nmax]; bool bipartit = 1; int cnt[2] = {0, 0}; void checkbip(int node, int trial) { if(atrcol[node] != 0) { if(atrcol[node] != trial) bipartit = 0; return; } cnt[0]++; if((light[node] ^ (trial - 1)) == 1) cnt[1]++; atrcol[node] = trial; for(auto x : g[node]) checkbip(x, 3 - trial); return; } signed main() { COMBI::init(); cin.tie(0) -> sync_with_stdio(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> light[i]; for(int x, y, i = 1; i <= m; i++) { cin >> x >> y; g[x].emplace_back(y); g[y].emplace_back(x); } Mint total = 1; for(int i = 1; i <= n; i++) { if(atrcol[i] == 0) { bipartit = 1; cnt[0] = cnt[1] = 0; checkbip(i, 1); //cerr << i << '\t' << cnt[0] << ' ' << cnt[1] << '\n'; if(bipartit == 0) total *= Mint(2) ^ (cnt[0] - 1); else total *= COMBI::ncr(cnt[0], cnt[1]); } } cout << total.val << '\n'; } /** Anul asta nu se da centroid -- Rugaciunile mele */ |