

LGV 引理

简介

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

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

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

定义

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

表示到的 每一条 路径的之和，即。

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

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

一组的不相交路径：是一条从到的路径（是一个排列），对于任何，和没有公共顶点。

表示排列的逆序对个数。

引理

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

证明请参考维基百科。

例题

例 1 CF348D Turtles

题意：有一个的格点棋盘，其中某些格子可走，某些格子不可走。有一只海龟从只能走到和的位置，求海龟从到的不相交路径数对取模之后的结果。。

比较直接的 LGV 引理的应用。考虑所有合法路径，发现从出发一定要经过，而到达终点一定要经过，则可立即选定。应用 LGV 引理可得答案为：

其中为图上的路径数，带有障碍格点的路径计数问题可以直接做一个的 dp，则易求。最终复杂度。

参考代码

  #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 hdu5852 Intersection is not allowed!

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

观察到如果路径不相交就一定是到，因此 LGV 引理中一定有，不需要考虑符号问题。边权设为，直接套用引理即可。

从到的路径条数相当于从步中选步向下走，所以。

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

复杂度为，其中是求逆元复杂度。

参考代码

  #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;
  }

本页面最近更新：2022/9/22 16:20:15，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, H-J-Granger, Ir1d, kenlig, lxdlam, memset0, ouuan, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

LGV 引理

简介

定义

引理

例题

评论