跳转至

# LGV 引理

## 简介

Lindström–Gessel–Viennot lemma，即 LGV 引理，可以用来处理有向无环图上不相交路径计数等问题．

前置知识：图论相关概念 中的基础部分、矩阵、高斯消元求行列式．

LGV 引理仅适用于 有向无环图．

## 定义

𝜔(𝑃)ω(P) 表示 𝑃 P 这条路径上所有边的边权之积．（路径计数时，可以将边权都设为 1 1）（事实上，边权可以为生成函数）

𝑒(𝑢,𝑣)e(u,v) 表示 𝑢 u 到 𝑣 v 的 每一条 路径 𝑃 P 的 𝜔(𝑃)ω(P) 之和，即 𝑒(𝑢,𝑣) =∑𝑃:𝑢→𝑣 𝜔(𝑃)e(u,v)=∑P:u→v ω(P)．

起点集合 𝐴 A，是有向无环图点集的一个子集，大小为 𝑛 n．

终点集合 𝐵 B，也是有向无环图点集的一个子集，大小也为 𝑛 n．

一组 𝐴 →𝐵 A→B 的不相交路径 𝑆 S：𝑆 𝑖 S i 是一条从 𝐴 𝑖 A i 到 𝐵 𝜎(𝑆)𝑖 B σ(S)i 的路径（𝜎(𝑆)σ(S) 是一个排列），对于任何 𝑖 ≠𝑗 i≠j，𝑆 𝑖 S i 和 𝑆 𝑗 S j 没有公共顶点．

𝑡(𝜎)t(σ) 表示排列 𝜎 σ 的逆序对个数．

## 引理

𝑀=⎡⎢ ⎢ ⎢ ⎢⎣𝑒(𝐴 1,𝐵 1)𝑒(𝐴 1,𝐵 2)⋯𝑒(𝐴 1,𝐵 𝑛)𝑒(𝐴 2,𝐵 1)𝑒(𝐴 2,𝐵 2)⋯𝑒(𝐴 2,𝐵 𝑛)⋮⋮⋱⋮𝑒(𝐴 𝑛,𝐵 1)𝑒(𝐴 𝑛,𝐵 2)⋯𝑒(𝐴 𝑛,𝐵 𝑛)⎤⎥ ⎥ ⎥ ⎥⎦M=[e(A 1,B 1)e(A 1,B 2)⋯e(A 1,B n)e(A 2,B 1)e(A 2,B 2)⋯e(A 2,B n)⋮⋮⋱⋮e(A n,B 1)e(A n,B 2)⋯e(A n,B n)]d e t⁡(𝑀)=∑𝑆:𝐴→𝐵(−1)𝑡(𝜎(𝑆))𝑛∏𝑖=1 𝜔(𝑆 𝑖)det⁡(M)=∑S:A→B(−1)t(σ(S))∏i=1 n ω(S i)

其中 ∑𝑆:𝐴→𝐵∑S:A→B 表示满足上文要求的 𝐴 →𝐵 A→B 的每一组不相交路径 𝑆 S．

### 证明

由行列式定义可得

d e t⁡(𝑀)=∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1 𝑒(𝑎 𝑖,𝑏 𝜎(𝑖))=∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1∑𝑃:𝑎 𝑖→𝑏 𝜎(𝑖)𝜔(𝑃)det⁡(M)=∑σ(−1)t(σ)∏i=1 n e(a i,b σ(i))=∑σ(−1)t(σ)∏i=1 n∑P:a i→b σ(i)ω(P)

观察到 𝑛∏𝑖=1∑𝑃:𝑎 𝑖→𝑏 𝜎(𝑖)𝜔(𝑃)∏i=1 n∑P:a i→b σ(i)ω(P)，实际上是所有从 𝐴 A 到 𝐵 B 排列为 𝜎 σ 的路径组 𝑃 P 的 𝜔(𝑃)ω(P) 之和．

∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1∑𝑃:𝑎 𝑖→𝑏 𝜎(𝑖)𝜔(𝑃)=∑𝜎(−1)𝑡(𝜎)∑𝑃=𝜎 𝜔(𝑃)=∑𝑃:𝐴→𝐵(−1)𝑡(𝜎)𝑛∏𝑖=1 𝜔(𝑃 𝑖)∑σ(−1)t(σ)∏i=1 n∑P:a i→b σ(i)ω(P)=∑σ(−1)t(σ)∑P=σ ω(P)=∑P:A→B(−1)t(σ)∏i=1 n ω(P i)

此处 𝑃 P 为任意路径组．

设 𝑈 U 为不相交路径组，𝑉 V 为相交路径组，

∑𝑃:𝐴→𝐵(−1)𝑡(𝜎)𝑛∏𝑖=1 𝜔(𝑃 𝑖)=∑𝑈:𝐴→𝐵(−1)𝑡(𝑈)𝑛∏𝑖=1 𝜔(𝑈 𝑖)+∑𝑉:𝐴→𝐵(−1)𝑡(𝑉)𝑛∏𝑖=1 𝜔(𝑉 𝑖)∑P:A→B(−1)t(σ)∏i=1 n ω(P i)=∑U:A→B(−1)t(U)∏i=1 n ω(U i)+∑V:A→B(−1)t(V)∏i=1 n ω(V i)

设 𝑃 P 中存在一个相交路径组 𝑃 𝑖 :𝑎 1 →𝑢 →𝑏 1,𝑃 𝑗 :𝑎 2 →𝑢 →𝑏 2 P i:a 1→u→b 1,P j:a 2→u→b 2，则必然存在和它相对的一个相交路径组 𝑃′𝑖 =𝑎 1 →𝑢 →𝑏 2,𝑃′𝑗 =𝑎 2 →𝑢 →𝑏 1 P i′=a 1→u→b 2,P j′=a 2→u→b 1，𝑃′P′ 的其他路径与 𝑃 P 相同．可得 𝜔(𝑃) =𝜔(𝑃′),𝑡(𝑃) =𝑡(𝑃′) ±1 ω(P)=ω(P′),t(P)=t(P′)±1．

因此我们有 ∑𝑉:𝐴→𝐵( −1)𝑡(𝜎)𝑛∏𝑖=1 𝜔(𝑉 𝑖) =0∑V:A→B(−1)t(σ)∏i=1 n ω(V i)=0．

则 d e t⁡(𝑀) =∑𝑈:𝐴→𝐵( −1)𝑡(𝑈)𝑛∏𝑖=1 𝜔(𝑈 𝑖)det⁡(M)=∑U:A→B(−1)t(U)∏i=1 n ω(U i)．

证毕1．

## 例题

例 1 CF348D Turtles

题意：有一个 𝑛 ×𝑚 n×m 的格点棋盘，其中某些格子可走，某些格子不可走．有一只海龟从 (𝑥,𝑦)(x,y) 只能走到 (𝑥 +1,𝑦)(x+1,y) 和 (𝑥,𝑦 +1)(x,y+1) 的位置，求海龟从 (1,1)(1,1) 到 (𝑛,𝑚)(n,m) 的不相交路径数对 1 0 9 +7 10 9+7 取模之后的结果．2 ≤𝑛,𝑚 ≤3 0 0 0 2≤n,m≤3000．

比较直接的 LGV 引理的应用．考虑所有合法路径，发现从 (1,1)(1,1) 出发一定要经过 𝐴 ={(1,2),(2,1)}A={(1,2),(2,1)}，而到达终点一定要经过 𝐵 ={(𝑛 −1,𝑚),(𝑛,𝑚 −1)}B={(n−1,m),(n,m−1)}，则 𝐴,𝐵 A,B 可立即选定．应用 LGV 引理可得答案为：

∣𝑓(𝑎 1,𝑏 1)𝑓(𝑎 1,𝑏 2)𝑓(𝑎 2,𝑏 1)𝑓(𝑎 2,𝑏 2)∣=𝑓(𝑎 1,𝑏 1)×𝑓(𝑎 2,𝑏 2)−𝑓(𝑎 1,𝑏 2)×𝑓(𝑎 2,𝑏 1)|f(a 1,b 1)f(a 1,b 2)f(a 2,b 1)f(a 2,b 2)|=f(a 1,b 1)×f(a 2,b 2)−f(a 1,b 2)×f(a 2,b 1)

其中 𝑓(𝑎,𝑏)f(a,b) 为图上 𝑎 →𝑏 a→b 的路径数，带有障碍格点的路径计数问题可以直接做一个 𝑂(𝑛 𝑚)O(n m) 的 dp，则 𝑓 f 易求．最终复杂度 𝑂(𝑛 𝑚)O(n m)．

参考代码

     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!

题意：有一个 𝑛 ×𝑛 n×n 的棋盘，一个棋子从 (𝑥,𝑦)(x,y) 只能走到 (𝑥,𝑦 +1)(x,y+1) 或 (𝑥 +1,𝑦)(x+1,y)，有 𝑘 k 个棋子，一开始第 𝑖 i 个棋子放在 (1,𝑎 𝑖)(1,a i)，最终要到 (𝑛,𝑏 𝑖)(n,b i)，路径要两两不相交，求方案数对 1 0 9 +7 10 9+7 取模．1 ≤𝑛 ≤1 0 5 1≤n≤10 5，1 ≤𝑘 ≤1 0 0 1≤k≤100，保证 1 ≤𝑎 1 <𝑎 2 <⋯ <𝑎 𝑛 ≤𝑛 1≤a 1<a 2<⋯<a n≤n，1 ≤𝑏 1 <𝑏 2 <⋯ <𝑏 𝑛 ≤𝑛 1≤b 1<b 2<⋯<b n≤n．

观察到如果路径不相交就一定是 𝑎 𝑖 a i 到 𝑏 𝑖 b i，因此 LGV 引理中一定有 𝜎(𝑆)𝑖 =𝑖 σ(S)i=i，不需要考虑符号问题．边权设为 1 1，直接套用引理即可．

从 (1,𝑎 𝑖)(1,a i) 到 (𝑛,𝑏 𝑗)(n,b j) 的路径条数相当于从 𝑛 −1 +𝑏 𝑗 −𝑎 𝑖 n−1+b j−a i 步中选 𝑛 −1 n−1 步向下走，所以 𝑒(𝐴 𝑖,𝐵 𝑗) =(𝑛−1+𝑏 𝑗−𝑎 𝑖 𝑛−1)e(A i,B j)=(n−1+b j−a i n−1)．

行列式可以使用高斯消元求．

复杂度为 𝑂(𝑛 +𝑘(𝑘 2 +l o g⁡𝑝))O(n+k(k 2+log⁡p))，其中 l o g⁡𝑝 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
    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;
    }

## 参考资料

1. 证明来源于 知乎 - LGV 引理证明 ↩

> 本页面最近更新：2026/1/30 21:35:24，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, Enter-tainer, Ir1d, ouuan, c-forrest, chenyichen0420, Cidoai, H-J-Granger, HeRaNO, kenlig, lxdlam, memset0, Menci
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用