OI-wiki 图论专题：LGV 引理——用行列式解决 DAG 不相交路径计数问题-平芜编程栈

OI-wiki 图论专题：LGV 引理——用行列式解决 DAG 不相交路径计数问题

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

Lindström–Gessel–Viennot 引理（简称 LGV 引理）是 OI / ICPC 竞赛中处理有向无环图（DAG）不相交路径计数问题的核心工具。它的威力在于：一组起点集合到一组终点集合的"不相交路径组"的带符号计数，恰好等于一个由两点间路径权值和构成的矩阵的行列式。阅读本文后，你将掌握 LGV 引理的严格数学定义、行列式证明思路，以及 CF348D Turtles 与 HDU 5852 两道经典例题的完整推导与参考实现、参考实现，能够独立将"棋盘/网格上两两不相交路径计数"类问题转化为行列式计算。

本文主体内容源自 OI-wiki 图论模块的 LGV 引理文档，并结合作者仓库中的配套源码与测试用例进行深度展开。

一、前置知识与适用前提

LGV 引理并不是一个"普适"的计数魔法，它有一项硬性前提：

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

这一点至关重要：引理证明中大量使用"路径组交换后缀后符号改变"的配对抵消论证，这要求图中不存在环，否则"路径"的定义与配对关系都会失效。

在深入学习之前，建议先熟悉以下前置知识（均在当前仓库中有对应文档）：

图论相关概念的基础部分：路径、排列、逆序对等；
矩阵基础：矩阵乘法、行列式展开的定义；
高斯消元求行列式：在点数较多时计算行列式的标准算法。

二、核心定义：路径权、路径和与不相交路径组

设 $G$ 是一个有向无环图，定义如下几个量：

1. 路径权值 $\omega(P)$

$\omega(P)$ 表示路径 $P$ 上所有边的边权之积。

做路径计数时，只需把所有边权都设为 $1$，此时 $\omega(P) \equiv 1$，一条路径的权值就是 $1$；
事实上边权还可以是生成函数，这为带权统计提供了极大的灵活性（例如给边权赋 $x$ 的幂次以统计长度分布）。

2. 路径权值和 $e(u, v)$

$e(u, v)$ 表示从 $u$ 到 $v$ 的每一条路径 $P$ 的 $\omega(P)$ 之和，即

$$e(u, v)=\sum_{P:u\rightarrow v}\omega(P)$$

当边权全为 $1$ 时，$e(u,v)$ 就是 $u$ 到 $v$ 的路径条数。可以直观地理解为"加权路径计数"。

3. 起点集合与终点集合

起点集合 $A={A_1,A_2,\dots,A_n}$：DAG 点集的一个大小为 $n$ 的子集；
终点集合 $B={B_1,B_2,\dots,B_n}$：DAG 点集的一个同样大小为 $n$ 的子集。

4. 不相交路径组 $S$

一组 $A\rightarrow B$ 的不相交路径 $S$ 满足：

$S_i$ 是一条从 $A_i$ 到 $B_{\sigma(S)_i}$ 的路径，其中 $\sigma(S)$ 是一个排列（即路径终点与起点之间是一个双射）；
对于任何 $i\ne j$，$S_i$ 和 $S_j$没有公共顶点（即两两顶点不相交）。

5. 排列的逆序对数 $t(\sigma)$

$t(\sigma)$ 表示排列 $\sigma$ 的逆序对个数。它决定了求和项前的符号 $(-1)^{t(\sigma)}$，这是行列式展开中天然出现的因子。

三、LGV 引理：行列式等于不相交路径组的带符号和

3.1 引理陈述

构造 $n\times n$ 矩阵 $M$，其元素为

$$ M = \begin{bmatrix} e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\ \vdots&\vdots&\ddots&\vdots\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n) \end{bmatrix} $$

则 LGV 引理断言：

$$ \det(M)=\sum_{S:A\rightarrow B}(-1)^{t(\sigma(S))}\prod_{i=1}^n \omega(S_i) $$

其中 $\sum\limits_{S:A\rightarrow B}$ 遍历满足上文要求的每一组$A\rightarrow B$ 不相交路径 $S$。

解读：行列式的值等于"所有不相交路径组的带符号权值之和"。也就是说，尽管 $e(u,v)$ 里混入了大量会相交的路径，行列式的展开与符号配对会自动把这些"相交路径组"全部抵消，只留下不相交的那些。

3.2 证明思路

第一步：按行列式定义展开。

由行列式定义：

$$ \begin{align} \det(M)&=\sum_{\sigma}(-1)^{t(\sigma)}\prod_{i=1}^n e(a_i,b_{\sigma(i)})\ &=\sum_{\sigma}(-1)^{t(\sigma)}\prod_{i=1}^n \sum_{P:a_i\to b_{\sigma(i)}} \omega(P) \end{align} $$

观察到 $\prod\limits_{i=1}^n \sum\limits_{P:a_i\to b_{\sigma(i)}} \omega(P)$ 实际上是所有排列为 $\sigma$ 的路径组 $P$的 $\omega(P)$ 之和，于是

$$ \begin{align} &\sum_{\sigma}(-1)^{t(\sigma)}\prod_{i=1}^n \sum_{P:a_i\to b_{\sigma(i)}} \omega(P)\ =&\sum_{\sigma}(-1)^{t(\sigma)}\sum_{P=\sigma}\omega(P)\ =&\sum_{P:A\to B}(-1)^{t(\sigma)}\prod_{i=1}^n \omega(P_i) \end{align} $$

此处 $P$ 为任意路径组（允许相交）。

第二步：把路径组分为不相交（$U$）与相交（$V$）两类。

$$ \begin{align} &\sum_{P:A\to B}(-1)^{t(\sigma)}\prod_{i=1}^n \omega(P_i)\ =&\sum_{U:A\to B}(-1)^{t(U)}\prod_{i=1}^n \omega(U_i)+\sum_{V:A\to B}(-1)^{t(V)}\prod_{i=1}^n \omega(V_i) \end{align} $$

第三步：关键配对抵消——相交路径组的贡献为 $0$。

设相交路径组 $P$ 中存在两条路径在顶点 $u$ 相交：

$$P_i:a_1 \to u \to b_1,\qquad P_j:a_2 \to u \to b_2$$

则必然存在与之配对的另一个相交路径组 $P'$：把这两条路径在 $u$ 之后的"后缀"交换，即

$$P_i'=a_1\to u\to b_2,\qquad P_j'=a_2\to u\to b_1$$

$P'$ 的其余路径与 $P$ 完全相同。

由于只交换了后缀，边权乘积不变，故 $\omega(P)=\omega(P')$；
交换两条路径的终点相当于交换排列中的两个元素，逆序对奇偶性改变，故 $t(P)=t(P')\pm 1$。

因此 $P$ 与 $P'$ 在求和 $\sum\limits_{V:A\to B}(-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(V_i)$ 中符号相反、权值相等，恰好成对抵消。于是

$$\sum_{V:A\to B}(-1)^{t(\sigma)}\prod_{i=1}^n \omega(V_i)=0$$

第四步：结论。

$$ \det(M)=\sum_{U:A\to B}(-1)^{t(U)}\prod_{i=1}^n \omega(U_i) $$

证毕。该证明思路与知乎 - LGV 引理证明一致（原文出处见 OI-wiki lgv 文档的参考资料脚注）。

证明的关键启示：LGV 引理的实用性建立在"相交路径可两两配对抵消"之上。这解释了为什么在实际应用中，我们常常只需关心"若路径不相交，则终点排列必然唯一确定"的情形——此时符号项可以完全忽略，答案就是行列式本身（详见第四节例题 2）。

四、经典例题实战

4.1 例 1：CF348D Turtles——2×2 行列式的直接应用

题目（Codeforces 348D）：有一个 $n\times m$ 的格点棋盘，某些格子可走、某些不可走。一只海龟从 $(x,y)$ 只能走到 $(x+1,y)$ 或 $(x,y+1)$，求海龟从 $(1,1)$ 到 $(n,m)$ 的不相交路径数对 $10^9+7$ 取模的结果。数据范围 $2\le n,m\le 3000$。

分析：这是 LGV 引理最直接的入门应用。

观察所有合法路径：从 $(1,1)$ 出发的第一步，必然经过 $A={(1,2),(2,1)}$ 中的某一点；
到达终点前的最后一步，必然经过 $B={(n-1,m),(n,m-1)}$ 中的某一点。

于是起点集合与终点集合立即确定为

$$A={a_1=(1,2),;a_2=(2,1)},\qquad B={b_1=(n-1,m),;b_2=(n,m-1)}$$

套用 LGV 引理（$n=2$ 情形，行列式是一个 $2\times 2$ 行列式）：

$$ \begin{vmatrix} f(a_1, b_1) & f(a_1, b_2) \ f(a_2, b_1) & f(a_2, b_2) \end{vmatrix} = 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\rightarrow b$ 的路径数。带有障碍格点的路径计数可以直接做 $O(nm)$ 的 DP 求得，因此总复杂度 $O(nm)$。

仓库配套实现位于 docs/graph/code/lgv/lgv_2.cpp，其关键结构为：

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

主程序对四组点对分别调用 $f$，再计算行列式并取模：

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;

实现要点（从源码结构可以归纳）：

棋盘输入时给每行前拼接一个空格字符（board[i] = " " + board[i]），使得下标从 $1$ 开始，避免越界判断；
DP 中先判#障碍、再累加上方与左方来源，保证dp值始终为模意义下的路径数；
减法结果+ MOD后再取模，避免出现负数。

配套测试数据在 docs/graph/examples/lgv/lgv_2.in 与 docs/graph/examples/lgv/lgv_2.ans：

// 输入：4×5 棋盘，中间两行有障碍 4 5 ..... .###. .###. ..... // 期望输出 1

从代码与样例可以验证：即使存在障碍格，只要把 $f$ 的 DP 做好、代入 $2\times2$ 行列式，就能得到正确的不相交路径数。

4.2 例 2：HDU 5852 Intersection is not allowed!——高斯消元求大行列式

题目（HDU 5852）：有一个 $n\times n$ 棋盘，棋子从 $(x,y)$ 只能走到 $(x,y+1)$ 或 $(x+1,y)$。有 $k$ 个棋子，第 $i$ 个棋子一开始放在 $(1,a_i)$，最终要到 $(n,b_i)$，路径要两两不相交，求方案数对 $10^9+7$ 取模。数据范围：$1\le n\le 10^5$，$1\le k\le 100$，并保证 $1\le a_1<a_2<\dots<a_k\le n$，$1\le b_1<b_2<\dots<b_k\le n$。

分析：

符号项消失的巧妙之处：观察到起点序列 $a_i$ 与终点序列 $b_i$ 都是严格递增的。在只能向下/向右走的棋盘上，如果两条路径不相交，则第 $i$ 个起点必然对应第 $i$ 个终点，即 $\sigma(S)_i=i$（恒等排列）。此时 $t(\sigma)=0$，LGV 引理中的符号问题完全消失，答案就是行列式本身。
组合数求 $e$：从 $(1,a_i)$ 到 $(n,b_j)$ 需要向右走 $b_j-a_i$ 步、向下走 $n-1$ 步，总共 $n-1+b_j-a_i$ 步中选择 $n-1$ 步向下，因此

$$e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}$$

行列式计算：$k\le 100$，直接使用高斯消元求行列式即可。

复杂度为 $O(n+k(k^2 + \log p))$，其中 $\log p$ 是求逆元的复杂度（$n$ 用于预处理阶乘，$k^2$ 是高斯消元主循环，$\log p$ 是每次求逆的快速幂代价）。

仓库配套实现位于 docs/graph/code/lgv/lgv_1.cpp，核心流程如下：

（1）预处理阶乘与组合数：

int qpow(int x, int y) { // 快速幂，用于求逆元 int out = 1; while (y) { if (y & 1) out = (ll)out * x % mod; x = (ll)x * x % mod; y >>= 1; } return out; } int c(int x, int y) { // 组合数 C(x, y) mod (1e9+7) return (ll)fact[x] * qpow(fact[y], mod - 2) % mod * qpow(fact[x - y], mod - 2) % mod; }

fact[0..2N]在主函数中先行递推：fact[i] = fact[i-1] * i % mod。由于模数 $10^9+7$ 是素数，可用费马小定理（$a^{p-2}$ 为 $a$ 的逆元）求组合数。

（2）构造 LGV 矩阵：

for (int i = 1; i <= k; ++i) { for (int j = 1; j <= k; ++j) { if (a[i] <= b[j]) m[i][j] = c(b[j] - a[i] + n - 1, n - 1); else m[i][j] = 0; // 起点在终点下方，路径数为 0 } }

注意a[i] > b[j]时矩阵元素直接置 $0$（向左上方向无法到达），这是网格图上 $e(A_i,B_j)$ 的边界条件。

（3）高斯消元化为上三角并累乘对角线：

for (int i = 1; i < k; ++i) { if (!m[i][i]) { // 主元为 0，寻找下方非零行交换 for (int j = i + 1; j <= k; ++j) { if (m[j][i]) { std::swap(m[i], m[j]); break; } } } if (!m[i][i]) continue; int inv = qpow(m[i][i], mod - 2); // 主元逆元 for (int j = i + 1; j <= k; ++j) { if (!m[j][i]) continue; int mul = (ll)m[j][i] * inv % mod; for (int p = i; p <= k; ++p) m[j][p] = (m[j][p] - (ll)m[i][p] * mul % mod + mod) % mod; } } int ans = 1; for (int i = 1; i <= k; ++i) ans = (ll)ans * m[i][i] % mod; // 对角线乘积

实现细节（源码可验证）：

消元过程中所有运算都在模 $10^9+7$ 下进行，使用long long承接乘法避免溢出；
换行操作会改变行列式符号，但本题最终答案为正数，代码通过消元后直接累乘对角线得到行列式的绝对值——实际上本题矩阵可证其行列式非负，故实现中未额外处理换行符号；
每次减法后+ mod再取模，保证中间值非负。

配套测试数据在 docs/graph/examples/lgv/lgv_1.in 与 docs/graph/examples/lgv/lgv_1.ans：

// 输入：T=1 组，n=5，k=2，起点 (1,1)(1,2)，终点 (5,3)(5,4) 1 5 2 1 2 3 4 // 期望输出 50

五、方法论总结：何时用 LGV、怎么用

5.1 适用特征识别

结合两道例题，可以总结出 LGV 引理的典型应用模式：

计数对象是"多起点 → 多终点、路径两两不相交"的方案数；
图必须是有向无环图（网格棋盘天然满足）；
需要能高效计算任意两点间的路径权值和 $e(u,v)$（计数时用 DP / 组合数，带权时用生成函数）；
若能论证"不相交 ⟹ 终点排列唯一"，则答案就是行列式本身，无需处理符号项——这是竞赛中最常见的形态。

5.2 通用解题框架

步骤	操作	参考实现
1. 选点	确定起点集合 $A$、终点集合 $B$（通常由题目结构直接给出或由必经点确定）	例 1：$A={(1,2),(2,1)}$
2. 求 $e$	计算每对 $(A_i,B_j)$ 的路径权值和	例 2：组合数公式
3. 构造矩阵	填 $k\times k$ 矩阵 $M_{ij}=e(A_i,B_j)$	lgv_1.cpp
4. 算行列式	小规模直接展开；$k$ 大时用高斯消元取模	例 2 的消元循环
5. 处理符号	排列唯一则忽略；否则需要带符号求和	例 1 的 $2\times2$ 展开

5.3 常见误区提醒

忘记 DAG 前提：把 LGV 引理套在含环图上会得到错误结果，配对抵消论证依赖无环性；
忽略符号项：只有当"不相交 ⟹ 排列唯一"（或能逐个枚举排列）时才可忽略 $(-1)^{t(\sigma)}$；
组合数越界：例 2 中 $n$ 可达 $10^5$，阶乘要预处理到 $2N$ 的量级（$N\times2=200005$，见源码constexpr int N = 100005），否则 $b_j-a_i+n-1$ 可能超过预处理的阶乘范围。