LGV 引理
简介
Lindström–Gessel–Viennot lemma，即 LGV 引理，可以用来处理有向无环图上不相交路径计数等问题．
前置知识：图论相关概念 中的基础部分、矩阵、高斯消元求行列式．
LGV 引理仅适用于 有向无环图 ．
定义
𝜔(𝑃)ω(P)
表示 𝑃P 这条路径上所有边的边权之积．（路径计数时，可以将边权都设为 11）（事实上，边权可以为生成函数）
𝑒(𝑢,𝑣)e(u,v) 表示 𝑢u 到 𝑣v 的 每一条 路径 𝑃P 的 𝜔(𝑃)ω(P) 之和，即 𝑒(𝑢,𝑣) =∑𝑃:𝑢→𝑣𝜔(𝑃)e(u,v)=∑P:u→vω(P)．
起点集合 𝐴A，是有向无环图点集的一个子集，大小为 𝑛n．
终点集合 𝐵B，也是有向无环图点集的一个子集，大小也为 𝑛n．
一组 𝐴 →𝐵A→B 的不相交路径 𝑆S：𝑆𝑖Si 是一条从 𝐴𝑖Ai 到 𝐵𝜎(𝑆)𝑖Bσ(S)i 的路径（𝜎(𝑆)σ(S) 是一个排列），对于任何 𝑖 ≠𝑗i≠j，𝑆𝑖Si 和 𝑆𝑗Sj 没有公共顶点．
𝑡(𝜎)t(σ) 表示排列 𝜎σ 的逆序对个数．
引理
𝑀=⎡⎢ ⎢ ⎢ ⎢⎣𝑒(𝐴1,𝐵1)𝑒(𝐴1,𝐵2)⋯𝑒(𝐴1,𝐵𝑛)𝑒(𝐴2,𝐵1)𝑒(𝐴2,𝐵2)⋯𝑒(𝐴2,𝐵𝑛)⋮⋮⋱⋮𝑒(𝐴𝑛,𝐵1)𝑒(𝐴𝑛,𝐵2)⋯𝑒(𝐴𝑛,𝐵𝑛)⎤⎥ ⎥ ⎥ ⎥⎦M=[e(A1,B1)e(A1,B2)⋯e(A1,Bn)e(A2,B1)e(A2,B2)⋯e(A2,Bn)⋮⋮⋱⋮e(An,B1)e(An,B2)⋯e(An,Bn)]det(𝑀)=∑𝑆:𝐴→𝐵(−1)𝑡(𝜎(𝑆))𝑛∏𝑖=1𝜔(𝑆𝑖)det(M)=∑S:A→B(−1)t(σ(S))∏i=1nω(Si)
其中 ∑𝑆:𝐴→𝐵∑S:A→B 表示满足上文要求的 𝐴 →𝐵A→B 的每一组不相交路径 𝑆S．
证明
由行列式定义可得
det(𝑀)=∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1𝑒(𝑎𝑖,𝑏𝜎(𝑖))=∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1∑𝑃:𝑎𝑖→𝑏𝜎(𝑖)𝜔(𝑃)det(M)=∑σ(−1)t(σ)∏i=1ne(ai,bσ(i))=∑σ(−1)t(σ)∏i=1n∑P:ai→bσ(i)ω(P)
观察到 𝑛∏𝑖=1∑𝑃:𝑎𝑖→𝑏𝜎(𝑖)𝜔(𝑃)∏i=1n∑P:ai→bσ(i)ω(P)，实际上是所有从 𝐴A 到 𝐵B 排列为 𝜎σ 的路径组 𝑃P 的 𝜔(𝑃)ω(P) 之和．
∑𝜎(−1)𝑡(𝜎)𝑛∏𝑖=1∑𝑃:𝑎𝑖→𝑏𝜎(𝑖)𝜔(𝑃)=∑𝜎(−1)𝑡(𝜎)∑𝑃=𝜎𝜔(𝑃)=∑𝑃:𝐴→𝐵(−1)𝑡(𝜎)𝑛∏𝑖=1𝜔(𝑃𝑖)∑σ(−1)t(σ)∏i=1n∑P:ai→bσ(i)ω(P)=∑σ(−1)t(σ)∑P=σω(P)=∑P:A→B(−1)t(σ)∏i=1nω(Pi)
此处 𝑃P 为任意路径组．
设 𝑈U 为不相交路径组，𝑉V 为相交路径组，
∑𝑃:𝐴→𝐵(−1)𝑡(𝜎)𝑛∏𝑖=1𝜔(𝑃𝑖)=∑𝑈:𝐴→𝐵(−1)𝑡(𝑈)𝑛∏𝑖=1𝜔(𝑈𝑖)+∑𝑉:𝐴→𝐵(−1)𝑡(𝑉)𝑛∏𝑖=1𝜔(𝑉𝑖)∑P:A→B(−1)t(σ)∏i=1nω(Pi)=∑U:A→B(−1)t(U)∏i=1nω(Ui)+∑V:A→B(−1)t(V)∏i=1nω(Vi)
设 𝑃P 中存在一个相交路径组 𝑃𝑖 :𝑎1 →𝑢 →𝑏1,𝑃𝑗 :𝑎2 →𝑢 →𝑏2Pi:a1→u→b1,Pj:a2→u→b2，则必然存在和它相对的一个相交路径组 𝑃′𝑖 =𝑎1 →𝑢 →𝑏2,𝑃′𝑗 =𝑎2 →𝑢 →𝑏1Pi′=a1→u→b2,Pj′=a2→u→b1，𝑃′P′ 的其他路径与 𝑃P 相同．可得 𝜔(𝑃) =𝜔(𝑃′),𝑡(𝑃) =𝑡(𝑃′) ±1ω(P)=ω(P′),t(P)=t(P′)±1．
因此我们有 ∑𝑉:𝐴→𝐵( −1)𝑡(𝜎)𝑛∏𝑖=1𝜔(𝑉𝑖) =0∑V:A→B(−1)t(σ)∏i=1nω(Vi)=0．
则 det(𝑀) =∑𝑈:𝐴→𝐵( −1)𝑡(𝑈)𝑛∏𝑖=1𝜔(𝑈𝑖)det(M)=∑U:A→B(−1)t(U)∏i=1nω(Ui)．
证毕1．
例题
例 1 CF348D Turtles
题意：有一个 𝑛 ×𝑚n×m 的格点棋盘，其中某些格子可走，某些格子不可走．有一只海龟从 (𝑥,𝑦)(x,y) 只能走到 (𝑥 +1,𝑦)(x+1,y) 和 (𝑥,𝑦 +1)(x,y+1) 的位置，求海龟从 (1,1)(1,1) 到 (𝑛,𝑚)(n,m) 的不相交路径数对 109 +7109+7 取模之后的结果．2 ≤𝑛,𝑚 ≤30002≤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(a1,b1)f(a1,b2)f(a2,b1)f(a2,b2)|=f(a1,b1)×f(a2,b2)−f(a1,b2)×f(a2,b1)
其中 𝑓(𝑎,𝑏)f(a,b) 为图上 𝑎 →𝑏a→b 的路径数，带有障碍格点的路径计数问题可以直接做一个 𝑂(𝑛𝑚)O(nm) 的 dp，则 𝑓f 易求．最终复杂度 𝑂(𝑛𝑚)O(nm)．
参考代码
---|---
例 2 [HDU 5852 Intersection is not allowed!](https://acm.hdu.edu.cn/showproblem.php?pid=5852)
题意：有一个 𝑛 ×𝑛n×n 的棋盘，一个棋子从 (𝑥,𝑦)(x,y) 只能走到 (𝑥,𝑦 +1)(x,y+1) 或 (𝑥 +1,𝑦)(x+1,y)，有 𝑘k 个棋子，一开始第 𝑖i 个棋子放在 (1,𝑎𝑖)(1,ai)，最终要到 (𝑛,𝑏𝑖)(n,bi)，路径要两两不相交，求方案数对 109 +7109+7 取模．1 ≤𝑛 ≤1051≤n≤105，1 ≤𝑘 ≤1001≤k≤100，保证 1 ≤𝑎1 <𝑎2 <⋯ <𝑎𝑛 ≤𝑛1≤a1<a2<⋯<an≤n，1 ≤𝑏1 <𝑏2 <⋯ <𝑏𝑛 ≤𝑛1≤b1<b2<⋯<bn≤n．
观察到如果路径不相交就一定是 𝑎𝑖ai 到 𝑏𝑖bi，因此 LGV 引理中一定有 𝜎(𝑆)𝑖 =𝑖σ(S)i=i，不需要考虑符号问题．边权设为 11，直接套用引理即可．
从 (1,𝑎𝑖)(1,ai) 到 (𝑛,𝑏𝑗)(n,bj) 的路径条数相当于从 𝑛 −1 +𝑏𝑗 −𝑎𝑖n−1+bj−ai 步中选 𝑛 −1n−1 步向下走，所以 𝑒(𝐴𝑖,𝐵𝑗) =(𝑛−1+𝑏𝑗−𝑎𝑖𝑛−1)e(Ai,Bj)=(n−1+bj−ain−1)．
行列式可以使用高斯消元求．
复杂度为 𝑂(𝑛 +𝑘(𝑘2 +log𝑝))O(n+k(k2+logp))，其中 log𝑝logp 是求逆元复杂度．
参考代码
---|---
参考资料
- 证明来源于 知乎 - 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 协议之条款下提供，附加条款亦可能应用