跳转至

LGV 引理

简介

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

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

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

定义

表示 这条路径上所有边的边权之积。(路径计数时,可以将边权都设为 )(事实上,边权可以为生成函数)

表示 每一条 路径 之和,即

起点集合 ,是有向无环图点集的一个子集,大小为

终点集合 ,也是有向无环图点集的一个子集,大小也为

一组 的不相交路径 是一条从 的路径( 是一个排列),对于任何 没有公共顶点。

表示排列 的逆序对个数。

引理

其中 表示满足上文要求的 的每一组不相交路径

证明

由行列式定义可得

观察到 ,实际上是所有从 排列为 的路径组 之和。

此处 为任意路径组。

为不相交路径组, 为相交路径组,

中存在一个相交路径组 ,则必然存在和它相对的一个相交路径组 的其他路径与 相同。可得

因此我们有

证毕1

例题

例 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 <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!

题意:有一个 的棋盘,一个棋子从 只能走到 ,有 个棋子,一开始第 个棋子放在 ,最终要到 ,路径要两两不相交,求方案数对 取模。,保证

观察到如果路径不相交就一定是 ,因此 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
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 引理证明