#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long int lli;
const int MAXN = 200005;
const lli MOD = 1000000007;
int t[MAXN];
vector<int> v[MAXN];
int lab[MAXN];
lli pot(lli a, int n) {
if (n == 0)
return 1;
if (n % 2 == 0)
return pot((a*a)%MOD, n/2);
else
return (a * pot(a, n-1)) % MOD;
}
lli rev(lli a) {
return pot(a, MOD-2);
}
lli fact[MAXN];
lli binom(lli n, lli k) {
// printf(" binom %lld %lld\n", n, k);
return (((fact[n] * rev(fact[k])) % MOD) * rev(fact[n-k])) % MOD;
}
bool found_conflict;
pair<pair<lli, lli>, pair<lli, lli>> sumuj(pair<pair<lli, lli>, pair<lli, lli>> a, pair<pair<lli, lli>, pair<lli, lli>> b) {
return {{a.st.st+b.st.st, a.st.nd+b.st.nd}, {a.nd.st+b.nd.st, a.nd.nd+b.nd.nd}};
}
// {{n_1, n_2}, {s_n_1, s_n_2}}
pair<pair<lli, lli>, pair<lli, lli>> dfs(int x, int l) {
lab[x] = l;
int tmp[4];
tmp[l] = 1;
tmp[3-l] = 0;
pair<pair<lli, lli>, pair<lli, lli>> res = {{tmp[1], tmp[2]}, {tmp[1]*t[x], tmp[2]*t[x]}};
for (int a : v[x]) {
if (lab[a] == l) {
// return {{MAXN, 0}, {0, 0}};
found_conflict = true;
}
if (lab[a] == 0)
res = sumuj(res, dfs(a, 3-l));
}
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
fact[0] = 1;
for (int i=1; i<=n; i++) {
fact[i] = (fact[i-1] * i) % MOD;
}
for (int i=0; i<n; i++) {
scanf("%d", &t[i]);
}
for (int i=0; i<m; i++) {
int a, b;
scanf("%d%d", &a, &b);
a--;
b--;
v[a].push_back(b);
v[b].push_back(a);
}
lli fin = 1;
for (int i=0; i<n; i++) {
if (lab[i] == 0) {
found_conflict = false;
auto r = dfs(i, 1);
if (found_conflict) {
fin = (fin * pot(2, r.st.st+r.st.nd-1)) % MOD;
// printf("full: (%lld %lld), (%lld %lld), %lld\n", r.st.st, r.st.nd, r.nd.st, r.nd.nd, fin);
} else {
fin = (fin * binom(r.st.st+r.st.nd, r.st.st + r.nd.nd - r.nd.st)) % MOD;
// printf("bicol: (%lld %lld), (%lld %lld), %lld\n", r.st.st, r.st.nd, r.nd.st, r.nd.nd, fin);
}
// printf(" %lld, %d\n", fin, found_conflict);
}
}
printf("%lld\n", fin);
return 0;
}
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 | #include <bits/stdc++.h> using namespace std; #define st first #define nd second typedef long long int lli; const int MAXN = 200005; const lli MOD = 1000000007; int t[MAXN]; vector<int> v[MAXN]; int lab[MAXN]; lli pot(lli a, int n) { if (n == 0) return 1; if (n % 2 == 0) return pot((a*a)%MOD, n/2); else return (a * pot(a, n-1)) % MOD; } lli rev(lli a) { return pot(a, MOD-2); } lli fact[MAXN]; lli binom(lli n, lli k) { // printf(" binom %lld %lld\n", n, k); return (((fact[n] * rev(fact[k])) % MOD) * rev(fact[n-k])) % MOD; } bool found_conflict; pair<pair<lli, lli>, pair<lli, lli>> sumuj(pair<pair<lli, lli>, pair<lli, lli>> a, pair<pair<lli, lli>, pair<lli, lli>> b) { return {{a.st.st+b.st.st, a.st.nd+b.st.nd}, {a.nd.st+b.nd.st, a.nd.nd+b.nd.nd}}; } // {{n_1, n_2}, {s_n_1, s_n_2}} pair<pair<lli, lli>, pair<lli, lli>> dfs(int x, int l) { lab[x] = l; int tmp[4]; tmp[l] = 1; tmp[3-l] = 0; pair<pair<lli, lli>, pair<lli, lli>> res = {{tmp[1], tmp[2]}, {tmp[1]*t[x], tmp[2]*t[x]}}; for (int a : v[x]) { if (lab[a] == l) { // return {{MAXN, 0}, {0, 0}}; found_conflict = true; } if (lab[a] == 0) res = sumuj(res, dfs(a, 3-l)); } return res; } int main() { int n, m; scanf("%d%d", &n, &m); fact[0] = 1; for (int i=1; i<=n; i++) { fact[i] = (fact[i-1] * i) % MOD; } for (int i=0; i<n; i++) { scanf("%d", &t[i]); } for (int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); a--; b--; v[a].push_back(b); v[b].push_back(a); } lli fin = 1; for (int i=0; i<n; i++) { if (lab[i] == 0) { found_conflict = false; auto r = dfs(i, 1); if (found_conflict) { fin = (fin * pot(2, r.st.st+r.st.nd-1)) % MOD; // printf("full: (%lld %lld), (%lld %lld), %lld\n", r.st.st, r.st.nd, r.nd.st, r.nd.nd, fin); } else { fin = (fin * binom(r.st.st+r.st.nd, r.st.st + r.nd.nd - r.nd.st)) % MOD; // printf("bicol: (%lld %lld), (%lld %lld), %lld\n", r.st.st, r.st.nd, r.nd.st, r.nd.nd, fin); } // printf(" %lld, %d\n", fin, found_conflict); } } printf("%lld\n", fin); return 0; } |
English