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:

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

#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();
}