Hướng giải của Đếm số phép gán thỏa mãn 2-SAT
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời giải
Phân tích
Sau khi tìm SCC của đồ thị khả năng:
- Nếu tồn tại biến \(x\) và \(\neg x\) trong cùng một SCC, số phép gán là 0 (vô nghiệm).
- Ngược lại, với mỗi cặp SCC đối xứng \((comp[x], comp[\neg x])\), có 2 cách chọn (chọn \(x = true\) hoặc \(x = false\)). Số phép gán là \(2^{k}\), với \(k\) là số cặp SCC.
Do mỗi biến \(x\) nằm trong một cặp SCC (cùng với \(\neg x\)), ta có:
- Số cặp SCC = \(N\) (vì mỗi biến tạo một cặp, và các cặp này độc lập).
Kết quả = \(2^N \mod (10^9 + 7)\) nếu có nghiệm, ngược lại là 0.
Độ phức tạp: \(O(N + M)\).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
int sz = 2 * n + 2;
vector<vector<int>> adj(sz), radj(sz);
auto add_impl = [&](int u, int v) {
adj[u].push_back(v);
radj[v].push_back(u);
};
for (int i = 0; i < m; i++) {
int a, b;
if (!(cin >> a >> b)) return 0;
int na = a > 0 ? 2 * a + 1 : 2 * (-a);
int nb = b > 0 ? 2 * b + 1 : 2 * (-b);
int a_node = a > 0 ? 2 * a : 2 * (-a) + 1;
int b_node = b > 0 ? 2 * b : 2 * (-b) + 1;
add_impl(na, b_node);
add_impl(nb, a_node);
}
vector<int> order, comp(sz, 0);
vector<bool> visited(sz, false);
function<void(int)> dfs1 = [&](int u) {
visited[u] = true;
for (int v : adj[u]) if (!visited[v]) dfs1(v);
order.push_back(u);
};
for (int i = 2; i <= 2 * n + 1; i++) if (!visited[i]) dfs1(i);
int comp_id = 0;
function<void(int)> dfs2 = [&](int u) {
comp[u] = comp_id;
for (int v : radj[u]) if (!comp[v]) dfs2(v);
};
for (int i = sz - 1; i >= 2; i--) {
int u = order[i];
if (!comp[u]) { comp_id++; dfs2(u); }
}
for (int i = 1; i <= n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { cout << "0\n"; return 0; }
}
long long ans = 1;
for (int i = 0; i < n; i++) {
ans = (ans * 2) % MOD;
}
cout << ans << "\n";
return 0;
}
Nhận xét