Skip to content

LGV Lemma

Introduction

The Lindström–Gessel–Viennot lemma, also known as the LGV lemma, can be used to handle problems such as counting non-intersecting paths on directed acyclic graphs.

Prerequisites: Basic concepts in Graph Theory, Matrices, and Gaussian Elimination for Determinants.

The LGV lemma applies only to directed acyclic graphs.

Definition

Let \(\omega(P)\) denote the product of the edge weights along path \(P\). (For path counting, all edge weights can be set to \(1\).) (In fact, edge weights can be generating functions.)

Let \(e(u, v)\) denote the sum of \(\omega(P)\) over every path \(P\) from \(u\) to \(v\), i.e., \(e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)\).

Let \(A\) be a set of starting vertices, a subset of the vertex set of the directed acyclic graph, with size \(n\).

Let \(B\) be a set of ending vertices, also a subset of the vertex set of the directed acyclic graph, with size \(n\).

A set of non-intersecting paths \(S\) from \(A\) to \(B\): \(S_i\) is a path from \(A_i\) to \(B_{\sigma(S)_i}\) (where \(\sigma(S)\) is a permutation), and for any \(i\ne j\), \(S_i\) and \(S_j\) share no common vertices.

Let \(t(\sigma)\) denote the number of inversions in permutation \(\sigma\).

Lemma

\[ 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) \]

Here, \(\sum\limits_{S:A\rightarrow B}\) denotes the sum over all sets \(S\) of non-intersecting paths from \(A\) to \(B\) satisfying the above requirements.

Proof

From the definition of determinant, we have

\[ \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} \]

Observe that \(\prod\limits_{i=1}^n \sum\limits_{P:a_i\to b_{\sigma(i)}} \omega(P)\) is essentially the sum of \(\omega(P)\) over all path groups \(P\) from \(A\) to \(B\) with permutation \(\sigma\).

\[ \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} \]

Here, \(P\) is any path group.

Let \(U\) be the set of non-intersecting path groups, and \(V\) be the set of intersecting path groups.

\[ \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} \]

Suppose in \(P\) there exists an intersecting path group \(P_i:a_1 \to u \to b_1, P_j:a_2 \to u \to b_2\). Then there must exist a corresponding intersecting path group \(P_i'=a_1\to u\to b_2, P_j'=a_2\to u\to b_1\), with all other paths in \(P'\) identical to those in \(P\). We have \(\omega(P)=\omega(P')\) and \(t(P)=t(P')\pm 1\).

Therefore, \(\sum\limits_{V:A\to B}(-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(V_i)=0\).

Thus, \(\det(M)=\sum\limits_{U:A\to B}(-1)^{t(U)}\prod\limits_{i=1}^n \omega(U_i)=0\).

Proof completed1.

Examples

Example 1 CF348D Turtles

Problem: Given an \(n\times m\) grid board, some cells are walkable and some are not. A turtle can only move from \((x, y)\) to \((x+1, y)\) or \((x, y+1)\). Find the number of non-intersecting paths for the turtle from \((1, 1)\) to \((n, m)\), modulo \(10^9+7\). \(2\le n,m\le3000\).

This is a straightforward application of the LGV lemma. Considering all valid paths, we observe that starting from \((1,1)\) must pass through \(A=\{(1,2), (2,1)\}\), and reaching the destination must pass through \(B=\{(n-1, m), (n, m-1)\}\). Thus, \(A\) and \(B\) can be immediately chosen. Applying the LGV lemma gives the answer:

\[ \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) \]

Here, \(f(a, b)\) is the number of paths from \(a\) to \(b\) on the graph. The path counting problem with obstacle cells can be solved directly with an \(O(nm)\) DP, so \(f\) is easy to compute. The overall complexity is \(O(nm)\).

Reference Code 
 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;
}
Example 2 HDU 5852 Intersection is not allowed!

Problem: Given an \(n\times n\) chessboard, a piece can only move from \((x, y)\) to \((x, y+1)\) or \((x + 1, y)\). There are \(k\) pieces, initially the \(i\)-th piece is at \((1, a_i)\), and finally must reach \((n, b_i)\). The paths must be pairwise non-intersecting. Find the number of such plans modulo \(10^9+7\). \(1\le n\le 10^5\), \(1\le k\le 100\), with \(1\le a_1<a_2<\dots<a_n\le n\) and \(1\le b_1<b_2<\dots<b_n\le n\).

Observe that if the paths are non-intersecting, they must go from \(a_i\) to \(b_i\). Therefore, in the LGV lemma, we must have \(\sigma(S)_i=i\), and the sign does not need to be considered. Set edge weights to \(1\) and directly apply the lemma.

The number of paths from \((1, a_i)\) to \((n, b_j)\) is equivalent to choosing \(n-1\) downward moves out of \(n-1+b_j-a_i\) steps, so \(e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}\).

The determinant can be computed using Gaussian elimination.

Complexity is \(O(n+k(k^2 + \log p))\), where \(\log p\) is the complexity for computing modular inverses.

Reference Code 
 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
77
78
79
80
#include <algorithm>
#include <iostream>

using ll = long long;

constexpr int K = 105;
constexpr int N = 100005;
constexpr 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;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  fact[0] = 1;
  for (int i = 1; i < N * 2; ++i) fact[i] = (ll)fact[i - 1] * i % mod;

  cin >> T;

  while (T--) {
    cin >> n >> k;

    for (int i = 1; i <= k; ++i) cin >> a[i];
    for (int i = 1; i <= k; ++i) cin >> 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;

    cout << ans << '\n';
  }

  return 0;
}

References

  1. The proof is adapted from Zhihu - Proof of LGV Lemma. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用