LGV 引理
阅读原文时间:2023年07月08日阅读:3

(其实是贺的:https://www.luogu.com.cn/paste/whl2joo4

目录

LGV 引理,即 Lindström–Gessel–Viennot lemma .

一个带权 DAG \(G\) 中有起点集 \(A=\{a_1, a_2, \cdots, a_n\}\),终点集 \(B=\{b_1, b_2, \cdots, b_n\}\) .

不相交路径定义为:一组 \(u\to v\) 的不相交路径 \(P=(P_1,P_2,\cdots,P_n)\),满足 \(P_i\) 是一条 \(a_i\) 到 \(b_{\sigma(P)_i}\) 的路径,其中 \(\sigma(P)\) 是 \(P\) 对应的排列 .

且对于任意 \(i\neq j\),\(P_i, P_j\) 无公共点(即不相交)

令 \(\omega(P)\) 为路径 \(P\) 上所有边权的积 .

对顶点 \(u,v\),定义

\[e(u,v) = \sum_{P:a \to b}{\omega(P)}
\]

令 \(\tau(p)\) 表示排列 \(p\) 的逆序对个数 .


令矩阵

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

则有

\[\boxed{\det(M)=\sum_{P:A\to B}{(-1)^{\tau(P)}\prod_{i=1}^{n}\omega(P_i)}}
\]

证明:

展开行列式的定义,得 LGV 引理等价于

\[\sum_p (-1)^{\tau(p)}\prod_{i=1}^ne(a_i, b_{p(i)})=\sum_{P:A\to B}{(-1)^{\tau(P)}\prod_{i=1}^{n}\omega(P_i)}
\]

其中 \(p\) 是一个 \(1\) 到 \(n\) 的排列 .

妈呀左右两边长得这么像!

观察组合意义!我们可以发现:

  • LHS 其实就是选 \(n\) 条起点和终点分别互不相同的路径,然后把他们的带符号和加起来 .
  • RHS 几乎一样,只不过 \(\displaystyle \sum_p\) 变成了 \(\displaystyle \sum_{P:A\to B}\),也就是要求路径不相交 .

故我们考虑构造双射 .

如果两个人的路径相交了,我们可以将相交后的部分取反,就相当于这两人分别走到了对方的终点去 . 这样是不是就不交了!!

是不是很平凡! 证明真牛逼 orz .


AJH 大佬说边权只要是交换环就行,也就是说可以是 GF .

太强了 orz

LGV 引理的直接应用 .

有一个图 \(G\) 是 平面图 且是 DAG .

从每个 \(a_i\) 到 \(b_i\),在满足路径不交的前提下,所有方案中路径边权乘积之和 .

是不是就是板子啊 .

你用一种方法算出 \(e\),然后是不是构造出 \(M\) 高斯消元求行列式就完了 .


为什么要是平面图?


一般的 LGV 题符合要求的匹配只有一组(e.g. 网格图),因此按照匹配的顺序列矩阵求出的就是不交路径数量 .

然而如果不是平面图,直接求 \(\det(M)\) 其实并不一定是不交路径数量 .

具体可以看 NOI2021 路径交点 .

Luogu6657. 【模板】LGV 引理

link: https://www.luogu.com.cn/problem/P6657


一个 \(n\times n\),每步只能往右下走 .

\(m\) 个棋子,初始在 \((a_i,1)\),要到 \((b_i,n)\) .

求不交路径方案数,对 \(998244353\) 取模 .

不相交路径计数 弱化版 .

显然对于任何一个路径,\(\omega(P)=1\),这样我们才能计数嘛 .

因为是网格图,所以拿出我们老生常谈的网格图两点路径计数:

\[e(u,v)=\dbinom{v-u+n-1}{n-1}
\]

(因为从 \((x_1,y_1)\) 到 \((x_2,y_2)\) 的方案数是 \(\dbinom{x_2-x_1+y_2-y_1}{x_2-x_1}\))

然后预处理阶乘及其逆元算 binom,然后高斯消元求行列式就完了 .

时间复杂度 \(O(n+m^3)\) .

CF348D Turtle

link: https://codeforces.com/contest/348/problem/D


网格图去掉一些点,两个点从 \((1,1)\) 走到 \((n,m)\),求不交路径数取模 \(10^9+7\) .

大力 LGV 引理 .

把两个相同起始点拆开,起点拆成 \((1,2)\),\((2,1)\),终点拆成 \((n-1,m)\),\((n,m-1)\) .

然后 LGV 引理可得一个二阶行列式,对角线法则乘开即可 .

然后变成带限制路径计数,做四边 DP 即可 .

时间复杂度 \(O(nm)\) .

Monotonic Matrix

link: https://www.nowcoder.com/acm/contest/139/A

求满足以下条件 \(n\times m\) 矩阵的数量:

  • \(A_{i,j}\in\{0, 1, 2\}\) .
  • \(A_{i,j}\le A_{i,j+1}\),\(A_{i,j}\le A_{i+1,j}\) .

对 \(10^9+7\) 取模 .

从起点 \((0,0)\) 终点 \((n,m)\) 画一条非降路径,然后 \(0,1\) 是沿着网格走的过程 .

从起点 \((-1,1)\) 终点 \((n-1,m+1)\) 画一条非降路径,然后 \(1,2\) 是沿着网格走的过程 .

然后用 LGV 引理算出不交的路径的方案数即可 .

然而这玩意也是二阶行列式,就是几个组合数乘一下减一下 .

时间复杂度在于求组合数 .

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章