#include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " " << x << endl; // #define int long long // uważaj const int N = 1e6 + 7, mod = 1e9 + 7; vector<int> uciekaj[N]; bitset<N> vis; vector<int> vek; int maski[N]; vector<int> G[N]; int n, m, a, b; void dfs(int v, int tu) { if(vis[v]) return; vis[v] = true; if(v > a and v <= a + b) uciekaj[tu].push_back(v), vek.push_back(v); for(auto x : G[v]) { dfs(x, tu); } } bool test(int mask) { for(int i = 1; i <= a; i++) { if(!(mask & maski[i])) return false; } return true; } int to_mask(int v) { int ret = 0; for(int i = 0; i < vek.size(); i++) { auto it = lower_bound(uciekaj[v].begin(), uciekaj[v].end(), vek[i]); if(it != uciekaj[v].end() and (*it) == vek[i]) { ret += (1 << i); } } return ret; } void solve() { cin >> n >> m >> a >> b; for(int i = 0; i < m; i++) { int a, b; string s; cin >> a >> s >> b; if(s[1] == '-') G[b].push_back(a); G[a].push_back(b); } for(int i = 1; i <= a; i++) { dfs(i, i); sort(uciekaj[i].begin(), uciekaj[i].end()); uciekaj[i].resize(unique(uciekaj[i].begin(), uciekaj[i].end()) - uciekaj[i].begin()); vis.reset(); } sort(vek.begin(), vek.end()); vek.resize(unique(vek.begin(), vek.end()) - vek.begin()); for(int i = 1; i <= a; i++) { maski[i] = to_mask(i); } int ans = 0; for(int i = 0; i < (1 << (int)vek.size()); i++) { if(test(i)) ans ++; if(ans > mod) ans -= mod; } for(int i = 0; i < b - (int)vek.size(); i++) { ans *= 2; if(ans > mod) ans -= mod; } cout << ans << endl; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int test = 1; while(test--){ solve(); } 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 | #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " " << x << endl; // #define int long long // uważaj const int N = 1e6 + 7, mod = 1e9 + 7; vector<int> uciekaj[N]; bitset<N> vis; vector<int> vek; int maski[N]; vector<int> G[N]; int n, m, a, b; void dfs(int v, int tu) { if(vis[v]) return; vis[v] = true; if(v > a and v <= a + b) uciekaj[tu].push_back(v), vek.push_back(v); for(auto x : G[v]) { dfs(x, tu); } } bool test(int mask) { for(int i = 1; i <= a; i++) { if(!(mask & maski[i])) return false; } return true; } int to_mask(int v) { int ret = 0; for(int i = 0; i < vek.size(); i++) { auto it = lower_bound(uciekaj[v].begin(), uciekaj[v].end(), vek[i]); if(it != uciekaj[v].end() and (*it) == vek[i]) { ret += (1 << i); } } return ret; } void solve() { cin >> n >> m >> a >> b; for(int i = 0; i < m; i++) { int a, b; string s; cin >> a >> s >> b; if(s[1] == '-') G[b].push_back(a); G[a].push_back(b); } for(int i = 1; i <= a; i++) { dfs(i, i); sort(uciekaj[i].begin(), uciekaj[i].end()); uciekaj[i].resize(unique(uciekaj[i].begin(), uciekaj[i].end()) - uciekaj[i].begin()); vis.reset(); } sort(vek.begin(), vek.end()); vek.resize(unique(vek.begin(), vek.end()) - vek.begin()); for(int i = 1; i <= a; i++) { maski[i] = to_mask(i); } int ans = 0; for(int i = 0; i < (1 << (int)vek.size()); i++) { if(test(i)) ans ++; if(ans > mod) ans -= mod; } for(int i = 0; i < b - (int)vek.size(); i++) { ans *= 2; if(ans > mod) ans -= mod; } cout << ans << endl; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int test = 1; while(test--){ solve(); } return 0; } |