LGV 引理
简介
Lindström–Gessel–Viennot lemma,即 LGV 引理,可以用来处理有向无环图上不相交路径计数等问题。
前置知识:图论相关概念 中的基础部分、矩阵、高斯消元求行列式。
LGV 引理仅适用于 有向无环图。
定义
𝜔(𝑃)
表示 𝑃
这条路径上所有边的边权之积。(路径计数时,可以将边权都设为 1
)(事实上,边权可以为生成函数)
𝑒(𝑢,𝑣)
表示 𝑢
到 𝑣
的 每一条 路径 𝑃
的 𝜔(𝑃)
之和,即 𝑒(𝑢,𝑣) =∑𝑃:𝑢→𝑣𝜔(𝑃)
。
起点集合 𝐴
,是有向无环图点集的一个子集,大小为 𝑛
。
终点集合 𝐵
,也是有向无环图点集的一个子集,大小也为 𝑛
。
一组 𝐴 →𝐵
的不相交路径 𝑆
:𝑆𝑖
是一条从 𝐴𝑖
到 𝐵𝜎(𝑆)𝑖
的路径(𝜎(𝑆)
是一个排列),对于任何 𝑖 ≠𝑗
,𝑆𝑖
和 𝑆𝑗
没有公共顶点。
𝑡(𝜎)
表示排列 𝜎
的逆序对个数。
引理
𝑀=⎡⎢
⎢
⎢
⎢⎣𝑒(𝐴1,𝐵1)𝑒(𝐴1,𝐵2)⋯𝑒(𝐴1,𝐵𝑛)𝑒(𝐴2,𝐵1)𝑒(𝐴2,𝐵2)⋯𝑒(𝐴2,𝐵𝑛)⋮⋮⋱⋮𝑒(𝐴𝑛,𝐵1)𝑒(𝐴𝑛,𝐵2)⋯𝑒(𝐴𝑛,𝐵𝑛)⎤⎥
⎥
⎥
⎥⎦
det(𝑀)=∑𝑆:𝐴→𝐵(−1)𝑡(𝜎(𝑆))𝑛∏𝑖=1𝜔(𝑆𝑖)
其中 ∑𝑆:𝐴→𝐵
表示满足上文要求的 𝐴 →𝐵
的每一组不相交路径 𝑆
。
证明
由行列式定义可得
det(𝑀)=∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1𝑒(𝑎𝑖,𝑏𝜎(𝑖))=∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1∑𝑃:𝑎𝑖→𝑏𝜎(𝑖)𝜔(𝑃)
观察到 𝑛∏𝑖=1∑𝑃:𝑎𝑖→𝑏𝜎(𝑖)𝜔(𝑃)
,实际上是所有从 𝐴
到 𝐵
排列为 𝜎
的路径组 𝑃
的 𝜔(𝑃)
之和。
∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1∑𝑃:𝑎𝑖→𝑏𝜎(𝑖)𝜔(𝑃)=∑𝜎(−1)𝑡(𝜎)∑𝑃=𝜎𝜔(𝑃)=∑𝑃:𝐴→𝐵(−1)𝑡(𝜎)𝑛∏𝑖=1𝜔(𝑃𝑖)
此处 𝑃
为任意路径组。
设 𝑈
为不相交路径组,𝑉
为相交路径组,
∑𝑃:𝐴→𝐵(−1)𝑡(𝜎)𝑛∏𝑖=1𝜔(𝑃𝑖)=∑𝑈:𝐴→𝐵(−1)𝑡(𝑈)𝑛∏𝑖=1𝜔(𝑈𝑖)+∑𝑉:𝐴→𝐵(−1)𝑡(𝑉)𝑛∏𝑖=1𝜔(𝑉𝑖)
设 𝑃
中存在一个相交路径组 𝑃𝑖 :𝑎1 →𝑢 →𝑏1,𝑃𝑗 :𝑎2 →𝑢 →𝑏2
,则必然存在和它相对的一个相交路径组 𝑃′𝑖 =𝑎1 →𝑢 →𝑏2,𝑃′𝑗 =𝑎2 →𝑢 →𝑏1
,𝑃′
的其他路径与 𝑃
相同。可得 𝜔(𝑃) =𝜔(𝑃′),𝑡(𝑃) =𝑡(𝑃′) ±1
。
因此我们有 ∑𝑉:𝐴→𝐵( −1)𝑡(𝜎)𝑛∏𝑖=1𝜔(𝑉𝑖) =0
。
则 det(𝑀) =∑𝑈:𝐴→𝐵( −1)𝑡(𝑈)𝑛∏𝑖=1𝜔(𝑈𝑖) =0
。
证毕[^1]。
例题
例 1 CF348D Turtles
题意:有一个 𝑛 ×𝑚
的格点棋盘,其中某些格子可走,某些格子不可走。有一只海龟从 (𝑥,𝑦)
只能走到 (𝑥 +1,𝑦)
和 (𝑥,𝑦 +1)
的位置,求海龟从 (1,1)
到 (𝑛,𝑚)
的不相交路径数对 109 +7
取模之后的结果。2 ≤𝑛,𝑚 ≤3000
。
比较直接的 LGV 引理的应用。考虑所有合法路径,发现从 (1,1)
出发一定要经过 𝐴 ={(1,2),(2,1)}
,而到达终点一定要经过 𝐵 ={(𝑛 −1,𝑚),(𝑛,𝑚 −1)}
,则 𝐴,𝐵
可立即选定。应用 LGV 引理可得答案为:
∣𝑓(𝑎1,𝑏1)𝑓(𝑎1,𝑏2)𝑓(𝑎2,𝑏1)𝑓(𝑎2,𝑏2)∣=𝑓(𝑎1,𝑏1)×𝑓(𝑎2,𝑏2)−𝑓(𝑎1,𝑏2)×𝑓(𝑎2,𝑏1)
其中 𝑓(𝑎,𝑏)
为图上 𝑎 →𝑏
的路径数,带有障碍格点的路径计数问题可以直接做一个 𝑂(𝑛𝑚)
的 dp,则 𝑓
易求。最终复杂度 𝑂(𝑛𝑚)
。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | #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!
题意:有一个 𝑛 ×𝑛
的棋盘,一个棋子从 (𝑥,𝑦)
只能走到 (𝑥,𝑦 +1)
或 (𝑥 +1,𝑦)
,有 𝑘
个棋子,一开始第 𝑖
个棋子放在 (1,𝑎𝑖)
,最终要到 (𝑛,𝑏𝑖)
,路径要两两不相交,求方案数对 109 +7
取模。1 ≤𝑛 ≤105
,1 ≤𝑘 ≤100
,保证 $1\le a_1
本页面最近更新:2025/10/13 16:54:57,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Tiphereth-A, Enter-tainer, Ir1d, ouuan, c-forrest, Cidoai, H-J-Granger, HeRaNO, kenlig, lxdlam, memset0, Menci
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用