LGV 引理

简介

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

前置知识：

图论相关概念 中的基础部分、

矩阵、

高斯消元求行列式。

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

定义

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

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

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

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

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

表示排列 的逆序对个数。

引理

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

证明请参考 维基百科。

例题

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

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

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

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

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

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