LGV 引理

简介

Lindström–Gessel–Viennot lemma，即 LGV 引理，可以用来处理有向无环图上不相交路径计数等问题。

前置知识：图论相关概念中的基础部分、矩阵、高斯消元求行列式。

LGV 引理仅适用于 有向无环图。

定义

$ω (P)$ 表示 $P$ 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 $1$ ）（事实上，边权可以为生成函数）

$e (u, v)$ 表示 $u$ 到 $v$ 的 每一条 路径 $P$ 的 $ω (P)$ 之和，即 $e (u, v) = \sum_{P : u \to v} ω (P)$ 。

起点集合 $A$ ，是有向无环图点集的一个子集，大小为 $n$ 。

终点集合 $B$ ，也是有向无环图点集的一个子集，大小也为 $n$ 。

一组 $A \to B$ 的不相交路径 $S$ ： $S_{i}$ 是一条从 $A_{i}$ 到 $B_{σ (S)_{i}}$ 的路径（ $σ (S)$ 是一个排列），对于任何 $i \neq j$ ， $S_{i}$ 和 $S_{j}$ 没有公共顶点。

$t (σ)$ 表示排列 $σ$ 的逆序对个数。

引理

M = [\begin{matrix} e (A_{1}, B_{1}) & e (A_{1}, B_{2}) & \dots & e (A_{1}, B_{n}) \\ e (A_{2}, B_{1}) & e (A_{2}, B_{2}) & \dots & e (A_{2}, B_{n}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ e (A_{n}, B_{1}) & e (A_{n}, B_{2}) & \dots & e (A_{n}, B_{n}) \end{matrix}]

\det (M) = \sum_{S : A \to B} (- 1)^{t (σ (S))} \prod_{i = 1}^{n} ω (S_{i})

其中 $\sum_{S : A \to B}$ 表示满足上文要求的 $A \to B$ 的每一组不相交路径 $S$ 。

证明

由行列式定义可得

\begin{aligned} \det (M) & = \sum_{σ} (- 1)^{t (σ)} \prod_{i = 1}^{n} e (a_{i}, b_{σ (i)}) \\ = \sum_{σ} (- 1)^{t (σ)} \prod_{i = 1}^{n} \sum_{P : a_{i} \to b_{σ (i)}} ω (P) \end{aligned}

观察到 $\prod_{i = 1}^{n} \sum_{P : a_{i} \to b_{σ (i)}} ω (P)$ ，实际上是所有从 $A$ 到 $B$ 排列为 $σ$ 的路径组 $P$ 的 $ω (P)$ 之和。

\begin{aligned} \sum_{σ} (- 1)^{t (σ)} \prod_{i = 1}^{n} \sum_{P : a_{i} \to b_{σ (i)}} ω (P) \\ = & \sum_{σ} (- 1)^{t (σ)} \sum_{P = σ} ω (P) \\ = & \sum_{P : A \to B} (- 1)^{t (σ)} \prod_{i = 1}^{n} ω (P_{i}) \end{aligned}

此处 $P$ 为任意路径组。

设 $U$ 为不相交路径组， $V$ 为相交路径组，

\begin{aligned} \sum_{P : A \to B} (- 1)^{t (σ)} \prod_{i = 1}^{n} ω (P_{i}) \\ = & \sum_{U : A \to B} (- 1)^{t (U)} \prod_{i = 1}^{n} ω (U_{i}) + \sum_{V : A \to B} (- 1)^{t (V)} \prod_{i = 1}^{n} ω (V_{i}) \end{aligned}

设 $P$ 中存在一个相交路径组 $P_{i} : a_{1} \to u \to b_{1}, P_{j} : a_{2} \to u \to b_{2}$ ，则必然存在和它相对的一个相交路径组 $P_{i}^{'} = a_{1} \to u \to b_{2}, P_{j}^{'} = a_{2} \to u \to b_{1}$ ， $P^{'}$ 的其他路径与 $P$ 相同。可得 $ω (P) = ω (P^{'}), t (P) = t (P^{'}) \pm 1$ 。

因此我们有 $\sum_{V : A \to B} (- 1)^{t (σ)} \prod_{i = 1}^{n} ω (V_{i}) = 0$ 。

则 $\det (M) = \sum_{U : A \to B} (- 1)^{t (U)} \prod_{i = 1}^{n} ω (U_{i}) = 0$ 。

证毕[^1]。

例题

例 1 CF348D Turtles

题意：有一个 $n \times m$ 的格点棋盘，其中某些格子可走，某些格子不可走。有一只海龟从 $(x, y)$ 只能走到 $(x + 1, y)$ 和 $(x, y + 1)$ 的位置，求海龟从 $(1, 1)$ 到 $(n, m)$ 的不相交路径数对 $10^{9} + 7$ 取模之后的结果。 $2 \leq n, m \leq 3000$ 。

比较直接的 LGV 引理的应用。考虑所有合法路径，发现从 $(1, 1)$ 出发一定要经过 $A = {(1, 2), (2, 1)}$ ，而到达终点一定要经过 $B = {(n - 1, m), (n, m - 1)}$ ，则 $A, B$ 可立即选定。应用 LGV 引理可得答案为：

| \begin{matrix} f (a_{1}, b_{1}) & f (a_{1}, b_{2}) \\ f (a_{2}, b_{1}) & f (a_{2}, b_{2}) \end{matrix} | = f (a_{1}, b_{1}) \times f (a_{2}, b_{2}) - f (a_{1}, b_{2}) \times f (a_{2}, b_{1})

其中 $f (a, b)$ 为图上 $a \to b$ 的路径数，带有障碍格点的路径计数问题可以直接做一个 $O (n m)$ 的 dp，则 $f$ 易求。最终复杂度 $O (n m)$ 。

参考代码

#include <cstring>
#include <iostream>
#include <string>

using namespace std;

using ll = long long;
constexpr int MOD = 1e9 + 7;
constexpr int SIZE = 3010;

string board[SIZE];
int dp[SIZE][SIZE];

int f(int x1, int y1, int x2, int y2) {
  memset(dp, 0, sizeof dp);

  dp[x1][y1] = board[x1][y1] == '.';
  for (int i = 1; i <= x2; i++) {
    for (int j = 1; j <= y2; j++) {
      if (board[i][j] == '#') {
        continue;
      }
      dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
      dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
    }
  }
  return dp[x2][y2] % MOD;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    cin >> board[i];
    board[i] = " " + board[i];
  }

  ll f11 = f(1, 2, n - 1, m);
  ll f12 = f(1, 2, n, m - 1);
  ll f21 = f(2, 1, n - 1, m);
  ll f22 = f(2, 1, n, m - 1);

  ll ans = ((f11 * f22) % MOD - (f12 * f21) % MOD + MOD) % MOD;
  cout << ans << '\n';

  return 0;
}

例 2 HDU 5852 Intersection is not allowed!

题意：有一个 $n \times n$ 的棋盘，一个棋子从 $(x, y)$ 只能走到 $(x, y + 1)$ 或 $(x + 1, y)$ ，有 $k$ 个棋子，一开始第 $i$ 个棋子放在 $(1, a_{i})$ ，最终要到 $(n, b_{i})$ ，路径要两两不相交，求方案数对 $10^{9} + 7$ 取模。 $1 \leq n \leq 10^{5}$ ， $1 \leq k \leq 100$ ，保证 $1\le a_1

本页面最近更新：2024/3/27 06:46:12，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, Enter-tainer, Ir1d, ouuan, Cidoai, H-J-Granger, kenlig, lxdlam, memset0, Menci
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用