LGV 引理小记

LGV 引理

设 \(G(V, E)\) 是一个 DAG，起点集 \(A = \{a_1, \dots, a_n\} \subseteq V\)，终点集 \(B = \{b_1, \dots, b_n\} \subseteq V\) 。

记 \(\omega_e\) 表示有向边 \(e\) 的边权，\(\omega_e\) 属于某个交换环。

对于有向路径 \(P\)，定义 \(\omega(P)\) 表示路径上边权的乘积，即 \[ \omega(P) = \prod\limits_{e \in P} \omega_e \] 对于任意两点 \(a, b\)，记 \(e(a, b)\) 表示从 \(a\) 到 \(b\) 的所有路径的权值之和，即 \[ e(a, b) = \sum\limits_{P:a\to b}\omega(P) \] 特别地，若 \(\omega_e=1\) ，\(e(a, b)\) 表示从 \(a\) 到 \(b\) 的路径数。

记矩阵 \[ M = \begin{pmatrix} 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{pmatrix} \] 定义从 \(A\) 到 \(B\) 的 \(n\) 元不相交路径组表示 \(G\) 中的 \(n\) 条有向路径 \((P_1, \dots, P_n)\) 满足：

存在 \(\{1, 2, \dots, n\}\) 的排列 \(\sigma\) 使得对于 \(i = 1, 2, \dots, n,\) 路径 \(P_i\) 是从 \(a_i\) 到 \(b_{\sigma_i}\) 的有向路径。
对于任意 \(i \neq j\)，路径 \(P_i, P_j\) 没有公共点。

记 \(\sigma(P)\) 表示 1 中的排列 \(\sigma\) 。

Lindström–Gessel–Viennot lemma \[ \det(M) = \sum\limits_{(P_1, P_2, \dots, P_n):A\to B} \operatorname{sgn}(\sigma(P))\prod_{i=1}^n\omega(P_i) \] 其中 \[ \operatorname{sgn}(\sigma(P)) = (-1)^{\pi(\sigma(P))} \] 特别地，若 \(\sigma(P)\) 只可能是 \(\{1, 2, \dots, n\}\) ，令 \(\omega_e=1\)，此时 \(\det(M)\) 等于 \(A\) 到 \(B\) 的不相交路径数。

证明略。

例题

NOI 2021Day1T2

// Author:  HolyK
// Created: Fri Jul 30 16:09:21 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
int det(std::vector<std::vector<int>> a) {
  int n = a.size(), r = 1, sgn = 1;
  for (int i = 0; i < n; i++) {
    int j = i;
    while (j < n && !a[j][i]) j++;
    if (j == n) return 0;
    if (i != j) std::swap(a[i], a[j]), sgn = -sgn;
    r = 1LL * r * a[i][i] % P;
    int inv = fpow(a[i][i]);
    for (j++; j < n; j++) {
      if (!a[j][i]) continue;
      int c = 1LL * a[j][i] * inv % P;
      for (int k = i; k < n; k++) {
        a[j][k] = (a[j][k] - 1LL * c * a[i][k]) % P;
      }
    }
  }
  return (P + r * sgn) % P;
}
void solve() {
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1), b(n - 1);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i + 1];  
  }
  for (int i = 1; i <= n; i++) {
    a[i] += a[i - 1];
  }
  for (int i = 0; i < n - 1; i++) {
    std::cin >> b[i];
  }
  std::vector<int> d(a.back());
  std::vector f(a[1], std::vector<int>(a[1]));
  for (int i = 0; i < a[1]; i++) f[i][i] = 1;
  for (int i = 0; i < n - 1; i++) {
    std::vector g(a[i + 2] - a[i + 1], std::vector<int>(a[1]));
    while (b[i]--) {
      int x, y;
      std::cin >> x >> y;
      x--, y--;
      for (int j = 0; j < a[1]; j++) {
        inc(g[y][j], f[x][j]);
      }
    }
    f.swap(g);
  }
  std::cout << det(f) << "\n";
}
int main() {
  freopen("xpath.in", "r", stdin);
  freopen("xpath.out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

最后修改于 2021-08-13