# 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↵
> ↵
> https://www.luogu.com.cn/article/3l93nkdh↵
↵
## 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:↵
↵
$$↵
2^{\text{count}} - 1↵
$$↵
↵
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↵
↵
$$↵
u \ dom \ w \ dom \ v↵
$$↵
↵
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:↵
↵
```cpp↵
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:↵
↵
$$↵
2^{\text{siz}} - 1↵
$$↵
↵
because any non-empty subset of this component is valid.↵
↵
So the total contribution from cells that lie on valid paths is:↵
↵
$$↵
\sum (2^{\text{siz}} - 1)↵
$$↵
↵
over all DSU components.↵
↵
Finally, don’t forget to add the contribution from cells that are not on any valid path:↵
↵
$$↵
2^{\text{count}} - 1↵
$$↵
↵
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:↵
↵
$$↵
O(V \log V)↵
$$↵
↵
since each grid cell has only constant out-degree.↵
↵
---↵
↵
[Submission](https://codeforces.me/contest/2247/submission/383524429)↵
↵
```cpp↵
#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();↵
}↵
```
↵
> 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↵
> ↵
> https://www.luogu.com.cn/article/3l93nkdh↵
↵
## 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:↵
↵
$$↵
2^{\text{count}} - 1↵
$$↵
↵
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↵
↵
$$↵
u \ dom \ w \ dom \ v↵
$$↵
↵
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:↵
↵
```cpp↵
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:↵
↵
$$↵
2^{\text{siz}} - 1↵
$$↵
↵
because any non-empty subset of this component is valid.↵
↵
So the total contribution from cells that lie on valid paths is:↵
↵
$$↵
\sum (2^{\text{siz}} - 1)↵
$$↵
↵
over all DSU components.↵
↵
Finally, don’t forget to add the contribution from cells that are not on any valid path:↵
↵
$$↵
2^{\text{count}} - 1↵
$$↵
↵
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:↵
↵
$$↵
O(V \log V)↵
$$↵
↵
since each grid cell has only constant out-degree.↵
↵
---↵
↵
[Submission](https://codeforces.me/contest/2247/submission/383524429)↵
↵
```cpp↵
#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();↵
}↵
```
