CF2247F — A More Intuitive Dominator-Tree Solution (Different from the Official Editorial)
This post was AI-translated from Chinese.
If you can read Chinese, I recommend the original Chinese write-up:
https://dk-qwq.github.io/blog/posts/cf2247/cf2247f/
or
Problem
You are given a grid graph where you may only move right or down. Each cell is marked with 0/1, indicating whether it is usable. $$$(1,1)$$$ is the start and $$$(n,m)$$$ is the destination.
We need to count how many non-empty sets of cells $$$S$$$ satisfy:
$$$\forall x, y \in S$$$, if a path from $$$(1,1)$$$ to $$$(n,m)$$$ passes through $$$x$$$, then it must also pass through $$$y$$$.
Solution
I want to present a solution that is much easier to come up with than the official one, although it requires a bit more code.
1. Two types of valid sets
A valid set $$$S$$$ can only be of two kinds:
- all cells in $$$S$$$ are blocked / unreachable / not contained in any valid $$$(1,1)\to(n,m)$$$ path;
- all cells in $$$S$$$ are cells that lie on valid paths.
For the first kind, the answer is obviously:
where count is the number of cells that are not on any valid start-to-end path.
So from now on, we only consider the second kind.
2. The relation between two cells
For any two cells $$$x, y$$$ in such a set, we must have:
- every valid path passing through $$$x$$$ also passes through $$$y$$$;
- every valid path passing through $$$y$$$ also passes through $$$x$$$.
This “must pass through” relation is exactly what dominator trees describe.
Since the grid with only right/down moves is a DAG, we can build a dominator tree for:
- the forward graph (from top-left to bottom-right),
- and the reversed graph (equivalently, considering the bottom-right to top-left direction).
Then the relation between $$$x$$$ and $$$y$$$ can be converted into domination relations on the forward and reverse dominator trees.
3. Why DSU works
Checking the domination relation for every pair $$$(x,y)$$$ would be too complicated.
Instead, observe the following:
Suppose
and $$$u$$$ and $$$v$$$ are mutually related (in the sense required by the problem). Then by the definition on the original graph, every path between $$$u$$$ and $$$v$$$ must also pass through $$$w$$$, so $$$w$$$ must belong to the set as well.
This means that the set of mutually related vertices must form a connected chain on the dominator tree, connected through parent-child edges.
Let:
fa1[u]be the parent of $$$u$$$ in the forward dominator tree,fa2[u]be the parent of $$$u$$$ in the reverse dominator tree.
Then the condition that two adjacent vertices are mutually related is equivalent to:
fa2[fa1[u]] == u
So we can simply check this condition for every vertex, and if it holds, merge u with fa1[u] in a DSU.
After that, each DSU component gives one maximal group of mutually valid cells. If a component has size siz, then it contributes:
because any non-empty subset of this component is valid.
So the total contribution from cells that lie on valid paths is:
over all DSU components.
Finally, don’t forget to add the contribution from cells that are not on any valid path:
Be careful not to double count any special edge case.
Complexity
Let $$$V = nm$$$.
Building the two dominator trees on DAGs and processing the DSU takes roughly:
since each grid cell has only constant out-degree.
#include <bits/stdc++.h>
#include <cassert>
#include <format>
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
using ll = long long;
class DAGDominatorTree {
public:
// vertices are numbered from 1 to n
// g[u] contains directed edges u -> v in the original graph
// the returned dominator tree has size n + 1, where 0 is a virtual root
vector<vector<int>> build(int n, const vector<vector<int>>& g) {
this->n = n;
LOG = __lg(max(1, n)) + 2;
G.assign(n + 1, {});
RG.assign(n + 1, {});
ST.assign(n + 1, {});
indeg.assign(n + 1, 0);
dep.assign(n + 1, 0);
fa.assign(n + 1, vector<int>(LOG, 0));
// copy the graph and build the reverse graph
for (int u = 1; u <= n; ++u) {
for (int v : g[u]) {
G[u].push_back(v);
RG[v].push_back(u);
++indeg[v];
}
}
// add virtual root: 0 -> all vertices with indegree 0
for (int u = 1; u <= n; ++u) {
if (indeg[u] == 0) {
G[0].push_back(u);
RG[u].push_back(0);
++indeg[u];
}
}
topoBuild();
// build the dominator tree
for (int u = 1; u <= n; ++u) {
ST[fa[u][0]].push_back(u);
}
return ST;
}
private:
int n, LOG;
vector<vector<int>> G, RG, ST, fa;
vector<int> indeg, dep;
int lca(int x, int y) {
if (x == 0 || y == 0) return x | y; // 0 acts as “null”
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
for (int k = 0; k < LOG; ++k) {
if (d >> k & 1) x = fa[x][k];
}
if (x == y) return x;
for (int k = LOG - 1; k >= 0; --k) {
if (fa[x][k] != fa[y][k]) {
x = fa[x][k];
y = fa[y][k];
}
}
return fa[x][0];
}
void topoBuild() {
queue<int> q;
q.push(0); // virtual root first
int cnt = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
++cnt;
if (u != 0) {
int p = 0;
for (int pre : RG[u]) p = lca(p, pre);
fa[u][0] = p;
dep[u] = dep[p] + 1;
for (int k = 1; k < LOG; ++k) {
fa[u][k] = fa[fa[u][k - 1]][k - 1];
}
}
for (int v : G[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
// the original graph is not a DAG
if (cnt != n + 1) {
throw runtime_error("Input graph is not a DAG.");
}
}
};
struct DSU{
vector<int> fa, siz;
void init(int n) {
fa.assign(n + 1, 0), siz.assign(n + 1, 1);
siz[0] = 0;
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return fa[x] == x? x: fa[x] = find(fa[x]);
}
bool Union(int x, int y) {
x = find(x), y = find(y);
if(x == y) return false;
if(siz[x] > siz[y]) swap(x, y);
fa[x] = y, siz[y] += siz[x];
return true;
}
}D;
const ll mod = 998244353;
ll qpow(ll x, ll k) {
ll res = 1;
while(k) {
if(k & 1ll) res = res * x % mod;
k >>= 1, x = x * x % mod;
}
return res;
}
void solve() {
DAGDominatorTree solver;
int n, m; cin >> n >> m;
int N = n * m;
auto encode = [&](int x, int y) -> int{
return (x - 1) * m + y;
};
auto decode = [&](int S) -> string {
int x = S / m, y = S % m;
if(y == 0) x--, y += m;
return format("({}, {})", x + 1, y);
};
vector a(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++) {
string s; cin >> s;
for(int j = 1; j <= m; j++)
a[i][j] = s[j - 1] - '0';
}
vector reach(n + 1, vector<bool>(m + 1, false));
reach[1][1] = true;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
if(a[i][j] == 0) continue;
if(reach[i - 1][j] || reach[i][j - 1])
reach[i][j] = true;
}
if(!reach[n][m]) {
return cout << qpow(2, n * m) - 1 << endl, void();
}
vector g(N + 1, vector<int>());
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
if(!reach[i][j]) continue;
if(reach[i - 1][j])
g[encode(i - 1, j)].push_back(encode(i, j));
if(reach[i][j - 1])
g[encode(i, j - 1)].push_back(encode(i, j));
}
vector reach2(n + 1 + 1, vector<bool>(m + 1 + 1, false));
reach2[n][m] = true;
for(int i = n; i >= 1; i--) for(int j = m; j >= 1; j--) {
if(a[i][j] == 0) continue;
if(reach2[i + 1][j] || reach2[i][j + 1])
reach2[i][j] = true;
}
vector gg(N + 1, vector<int>());
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
if(!reach2[i][j]) continue;
if(reach2[i - 1][j])
gg[encode(i, j)].push_back(encode(i - 1, j));
if(reach2[i][j - 1])
gg[encode(i, j)].push_back(encode(i, j - 1));
}
auto ST1 = solver.build(N, g);
auto ST2 = solver.build(N, gg);
vector<int> fa1(N + 1, 0);
vector<int> fa2(N + 1, 0);
for(int u = 1; u <= N; u++) for(auto v: ST1[u])
fa1[v] = u;
for(int u = 1; u <= N; u++) for(auto v: ST2[u])
fa2[v] = u;
D.init(N);
for(int u = 1; u <= N; u++) {
if(fa2[fa1[u]] != u) continue;
assert(fa1[u] > 0);
D.Union(u, fa1[u]);
}
ll ans = 0;
vector<bool> vis(N + 1, false);
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
if(!reach[i][j] || !reach2[i][j]) continue;
int r = D.find(encode(i, j));
if(vis[r]) continue;
vis[r] = true;
int sz = D.siz[r];
ans += qpow(2, sz) - 1;
ans %= mod;
}
int count = 0;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)
if(!reach[i][j] || !reach2[i][j]) count++;
if(count)
cout << (ans + qpow(2, count) - 1) % mod << endl;
else
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
cin >> T;
while(T--) solve();
}
Auto comment: topic has been updated by dkdk (previous revision, new revision, compare).