LGV 引理
簡介
Lindström–Gessel–Viennot lemma，即 LGV 引理，可以用來處理有向無環圖上不相交路徑計數等問題。
前置知識：圖論相關概念 中的基礎部分、矩陣、高斯消元求行列式。
LGV 引理僅適用於 有向無環圖。
定義
\(\omega(P)\) 表示 \(P\) 這條路徑上所有邊的邊權之積。（路徑計數時，可以將邊權都設為 \(1\)）（事實上，邊權可以為生成函數）
\(e(u, v)\) 表示 \(u\) 到 \(v\) 的 每一條 路徑 \(P\) 的 \(\omega(P)\) 之和，即 \(e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)\)。
起點集合 \(A\)，是有向無環圖點集的一個子集，大小為 \(n\)。
終點集合 \(B\)，也是有向無環圖點集的一個子集，大小也為 \(n\)。
一組 \(A\rightarrow B\) 的不相交路徑 \(S\)：\(S_i\) 是一條從 \(A_i\) 到 \(B_{\sigma(S)_i}\) 的路徑（\(\sigma(S)\) 是一個排列），對於任何 \(i\ne j\)，\(S_i\) 和 \(S_j\) 沒有公共頂點。
\(t(\sigma)\) 表示排列 \(\sigma\) 的逆序對個數。
引理
\[
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}
\]
\[
\det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{t(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i)
\]
其中 \(\sum\limits_{S:A\rightarrow B}\) 表示滿足上文要求的 \(A\rightarrow B\) 的每一組不相交路徑 \(S\)。
證明
由行列式定義可得
\[
\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)\)，實際上是所有從 \(A\) 到 \(B\) 排列為 \(\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}
\]
設 \(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\) 相同。可得 \(\omega(P)=\omega(P'),t(P)=t(P')\pm 1\)。
因此我們有 \(\sum\limits_{V:A\to B}(-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(V_i)=0\)。
則 \(\det(M)=\sum\limits_{U:A\to B}(-1)^{t(U)}\prod\limits_{i=1}^n \omega(U_i)=0\)。
證畢。
例題
例 1 CF348D Turtles
題意：有一個 \(n\times m\) 的格點棋盤，其中某些格子可走，某些格子不可走。有一隻海龜從 \((x, y)\) 只能走到 \((x+1, y)\) 和 \((x, y+1)\) 的位置，求海龜從 \((1, 1)\) 到 \((n, m)\) 的不相交路徑數對 \(10^9+7\) 取模之後的結果。\(2\le n,m\le3000\)。
比較直接的 LGV 引理的應用。考慮所有合法路徑，發現從 \((1,1)\) 出發一定要經過 \(A=\{(1,2), (2,1)\}\)，而到達終點一定要經過 \(B=\{(n-1, m), (n, m-1)\}\)，則 \(A, B\) 可立即選定。應用 LGV 引理可得答案為：
\[
\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，則 \(f\) 易求。最終複雜度 \(O(nm)\)。
參考代碼
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!
題意：有一個 \(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_n\le n\)，\(1\le b_1<b_2<\dots<b_n\le n\)。
觀察到如果路徑不相交就一定是 \(a_i\) 到 \(b_i\)，因此 LGV 引理中一定有 \(\sigma(S)_i=i\)，不需要考慮符號問題。邊權設為 \(1\)，直接套用引理即可。
從 \((1, a_i)\) 到 \((n, b_j)\) 的路徑條數相當於從 \(n-1+b_j-a_i\) 步中選 \(n-1\) 步向下走，所以 \(e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}\)。
行列式可以使用高斯消元求。
複雜度為 \(O(n+k(k^2 + \log p))\)，其中 \(\log p\) 是求逆元複雜度。
參考代碼
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;
}
|
參考資料
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用