CF1111 F 题解 - dk-qwq blog

F. Paths on a Grid #

题意#

给定一个网格图，只能往右和往下走，0/1 表示是否能到达， $(1, 1)$ ， $(n, m)$ 分别为起点，终点。

求问有多少非空点集 $S$ 使得 $\forall x, y \in S$ ，若 $(1, 1)$ 到 $(n, m)$ 的路径经过 $x$ 则必定经过 $y$ 。

题解#

介绍一种相较于官解非常好想但是代码量较多的做法。

$S$ 只有两种情况。

全部由堵塞或不能到达的格子构成
全部由在路径上的格子构成

前者显然为 $2^{count} - 1$ ，其中 $count$ 为不能到达的格子数，下文只考虑后者。

考虑集合内任意两点 $x, y$ 的关系，一定有经过 $x$ 的路径也经过 $y$ ，反之亦然。这种必定经过的关系符合支配树的定义。

对于网格图的右下方向和左上方向的可以建立一个DAG，由此建立支配树。

$x, y$ 的关系转化为了在正反图支配树上分别支配的关系。

但是这样每个 $x, y$ 都要验证支配关系太复杂了，假设 $u \ dom \ w \ dom \ v$ ，且 $u$ 和 $v$ 互相支配，那么根据原图上的定义， $u$ 和 $v$ 之间的路径一定经过 $w$ ，所以 $w$ 也在集合中。说明互相支配的关系集合一定在支配树上是能通过父子关系连接。

令 $fa1, fa2$ 分别为正反图支配树的父节点，那么上述相邻互相支配的关系等价于 $fa2[fa1[u]] == u$ ，我们对于每个节点 check 一下，然后在 dsu 上合并，最后统计每个连通块的大小，计算 $\sum (2^{siz} - 1)$ 。

记得加上前面统计的 $2^{count} - 1$ ，注意不要重复某种神秘的情况。

提交记录。

249 collapsed lines
#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:
    // 点编号: 1 ~ n
    // g[u] 表示原图中的有向边 u -> v
    // 返回的 ST 大小为 n + 1，其中 0 是虚拟根
    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));

        // 拷贝原图，并建反图
        for (int u = 1; u <= n; ++u) {
            for (int v : g[u]) {
                G[u].push_back(v);
                RG[v].push_back(u);
                ++indeg[v];
            }
        }

        // 加虚拟根 0 -> 所有入度为 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();

        // 建支配树
        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 当作“空值”
        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);  // 虚拟根先入队

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

        // 说明原图不是 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];
        // cout << sz << endl;
        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);
  // freopen("A.in", "r", stdin);
  // freopen("A.out", "w", stdout);
  int T = 1;
  cin >> T;
  while(T--) solve();
}

F. Paths on a Grid#

题意#

题解#

F. Paths on a Grid #