LGV 引理
简介
Lindström–Gessel–Viennot lemma，即 LGV 引理，可以用来处理有向无环图上不相交路径计数等问题。
前置知识：图论相关概念 中的基础部分、矩阵、高斯消元求行列式。
LGV 引理仅适用于 有向无环图。
定义
表示 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 ）（事实上，边权可以为生成函数）
表示 到 的 每一条 路径 的 之和，即 。
起点集合 ，是有向无环图点集的一个子集，大小为 。
终点集合 ，也是有向无环图点集的一个子集，大小也为 。
一组 的不相交路径 ： 是一条从 到 的路径（ 是一个排列），对于任何 ， 和 没有公共顶点。
表示排列 的逆序对个数。
引理
其中 表示满足上文要求的 的每一组不相交路径 。
证明
由行列式定义可得
观察到 ，实际上是所有从 到 排列为 的路径组 的 之和。
此处 为任意路径组。
设 为不相交路径组， 为相交路径组，
设 中存在一个相交路径组 ，则必然存在和它相对的一个相交路径组 ， 的其他路径与 相同。可得 。
因此我们有 。
则 。
证毕。
例题
例 1 CF348D Turtles
题意：有一个 的格点棋盘，其中某些格子可走，某些格子不可走。有一只海龟从 只能走到 和 的位置，求海龟从 到 的不相交路径数对 取模之后的结果。。
比较直接的 LGV 引理的应用。考虑所有合法路径，发现从 出发一定要经过 ，而到达终点一定要经过 ，则 可立即选定。应用 LGV 引理可得答案为：
其中 为图上 的路径数，带有障碍格点的路径计数问题可以直接做一个 的 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 <vector>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
const int SIZE = 3010;
char board[SIZE][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);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> (board[i] + 1);
}
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!
题意：有一个 的棋盘，一个棋子从 只能走到 或 ，有 个棋子，一开始第 个棋子放在 ，最终要到 ，路径要两两不相交，求方案数对 取模。，，保证 ，。
观察到如果路径不相交就一定是 到 ，因此 LGV 引理中一定有 ，不需要考虑符号问题。边权设为 ，直接套用引理即可。
从 到 的路径条数相当于从 步中选 步向下走，所以 。
行列式可以使用高斯消元求。
复杂度为 ，其中 是求逆元复杂度。
参考代码
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76 | #include <algorithm>
#include <cstdio>
typedef long long ll;
const int K = 105;
const int N = 100005;
const int mod = 1e9 + 7;
int T, n, k, a[K], b[K], fact[N << 1], m[K][K];
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) {
return (ll)fact[x] * qpow(fact[y], mod - 2) % mod *
qpow(fact[x - y], mod - 2) % mod;
}
int main() {
fact[0] = 1;
for (int i = 1; i < N * 2; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);
for (int i = 1; i <= k; ++i) scanf("%d", a + i);
for (int i = 1; i <= k; ++i) scanf("%d", b + i);
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;
}
}
for (int i = 1; i < k; ++i) {
if (!m[i][i]) {
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;
printf("%d\n", ans);
}
return 0;
}
|
参考资料
本页面最近更新：2024/3/27 06:46:12，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Cidoai, Enter-tainer, H-J-Granger, Ir1d, kenlig, lxdlam, memset0, Menci, ouuan, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用