LGV定理

wjyppm1403 · 2025-07-29 15:30:14 · 算法·理论

可能更好的阅读体验

0. 前言

你需要掌握的知识：

矩阵与矩阵运算。
行列式。

1. 概念与应用

1.1 概念

LGV 引理是用于解决图上不交路径计数的问题。同时也是线性代数中行列式的一个经典应用。

我们阐述一下概念。

对于一张有边权的有向无环图 G，定义一条路径 P，的权值 w(P) 为路径上所有边的边权的乘积，也就是说 w(P)=\prod_{(u,v)\in P} val(u,v)。

定义 e(u,v) 为 u \to v 的所有路径 P 的权值之和，也就是 \sum_{P:u\to v} w(P)。

定义两个大小为 n 的点集的子集 A,B，分别称之为起点集合与终点集合，则一组从 A\to B 的不交路径 S 为：S_i 是一条从 A_i \to B_{\sigma(S)_i}。其中 \sigma(S) 是一个与 S 对应的排列，对于任何 i\neq j，路径 S_i,S_j 不存在公共点。

而 LGV 引理说的就是，对于矩阵：

e(A_1,B_1) & e(A_1,B_2) & \dots & e(A_1,B_n)\\ e(A_2,B_1) & e(A_2,B_2) & \dots & e(A_2,B_n) \\ \vdots & \vdots & \ddots & \vdots \\ e(A_n,B_1) & e(A_n,B_2) & \dots & e(A_n,B_n) \end{bmatrix}

有 \det M=\sum_{S:A\to B} (-1)^{t(\sigma(S))} \prod_{i=1}^n w(S_i)，其中 t 表示一个排列的逆序对数的奇偶性。

1.2 证明

我们从排列展开公式出发，令 \operatorname{sgn}=(-1)^{t(\sigma(S))}：

\det M = \sum_{\sigma\in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n e(A_i, B_{\sigma(i)})

其中每个 e(A_i, B_{\sigma(i)}) 是从 A_i 到 B_{\sigma(i)} 的所有路径 P 的权值之和，即：

e(A_i, B_{\sigma(i)}) = \sum_{P_i: A_i \to B_{\sigma(i)}} w(P_i)

将这个表达代入上式得：

\det M = \sum_{\sigma\in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n \left( \sum_{P_i: A_i \to B_{\sigma(i)}} w(P_i) \right)

将乘积与求和交换：

\det M = \sum_{\sigma\in S_n} \operatorname{sgn}(\sigma) \sum_{P_1: A_1 \to B_{\sigma(1)}} \dots \sum_{P_n: A_n \to B_{\sigma(n)}} \prod_{i=1}^n w(P_i)

此时每一项对应的是从 A_i 到 B_{\sigma(i)} 的路径组 (P_1, \dots, P_n)，上式可以重写为：

\det M = \sum_{S} \operatorname{sgn}(\sigma(S)) \cdot w(S)

接下来将路径 S 分为两类：

若 S 中的所有路径两两点集不交，则称为不交路径，其对 \det M 的贡献为 \operatorname{sgn}(\sigma(S)) \cdot w(S)；
若 S 中存在交点（即某个点被多个路径共用），我们称其为交叉路径。

我们将证明所有交叉路径系统的贡献之和为 0。

为此，我们构造一个反对称配对消去所有交叉路径系统的贡献。考虑任意一个交叉路径系统 S，我们从中选出编号最小的交点 x，并设其在路径 P_i 与 P_j 中都出现，且 i<j。我们定义一个变换 \phi：

将路径 P_i 和 P_j 交换它们在交点 x 之后的部分，构造出新的路径 P_i', P_j'；
新的路径组 S' = (P_1, \dots, P_i', \dots, P_j', \dots, P_n)，对应的新排列 \sigma' 为 \sigma 与 (i,j) 交换；
由于 w(P_i')w(P_j') = w(P_i)w(P_j)，有 w(S') = w(S)；
但 \operatorname{sgn}(\sigma') = -\operatorname{sgn}(\sigma)。

因此，每一组交叉路径系统 S 与其配对路径系统 S' 贡献相反，抵消为 0。

因此最终仅剩下所有不交路径系统的贡献，证毕。

1.3 应用

说了这么多，由于是对不交路径组的带符号求和，所以 LGV 引理难以直接统计所有不交路径组的权值和。但是我们在实际解决问题的时候会有如下的方案：

题目就是让你求带符号的的答案。
图是特殊的图，是的不交路径的起点和终点对应是固定的，只存在一种或奇偶性相同的几种 \sigma(S)。只需要检验不交路径组的存在性，考虑给边随机赋权，检查 \det M \neq 0 即可。错误概率在 \dfrac{1}{P}，其中 P 为给随机赋权取模的模数。

2. 例题

CF348D Turtle

为数不多的几个超级模板题。首先考虑固定起始点的路径如何计算，我们可以通过 DP，求解，设 f(i,j) 表示从起始点到当前点 (i,j) 的方案数，显然转移：

\begin{cases} 0 & (i,j)\text{ 有障碍物} \\ f(i-1,j)+f(i,j-1) & (i,j) \text{ 无障碍物} \end{cases}

将起始点初始化为 1 即可，转移是 O(n^2) 的，很舒服。

但是怎么求不交路径呢？那么当然要用我们的 LGV 引理啦，毕竟方格图上的走法也可以算是一个有向无环图，而且只要我们把边权赋值为方案数就可以啦。

但是问题在于起点集合和终点集合怎么算，如果我们直接设置为 A=\{ (1,1) \},B=\{ (n,m)\} 的话那起点集合和终点集合本身两只乌龟就是重的啊，所以不能这么设置，但是我们额可以这么设置，这两只乌龟一定是一只从 (1,2) \to (n-1,m)，另一只是 (2,1) \to (n,m-1)，如果不是这么走的话显然是会相交的，那么我们的起点集合和终点集合就可以显然的设置了，就是按照上面两组进行设置，那么 2\times 2 的行列式计算如下：

a & b\\ c & d \end{vmatrix}=ad-bc

但是 a,b,c,d 怎么设置呢？根据我们说的，不可能存在 (1,2) \to (n,m-1),(2,1)\to (n-1,m) 的方案，所以我们这么设置。

令 (1,2) 走到 (n-1,m),(n,m-1) 的路径方案数为 a,b，令 (2,1) 走到 (n-1,m),(n,m-1) 的路径方案数为 c,d。答案还是 ad-bc，直接算就可以了。

P6657 LGV引理板子

还是方格图，但是这里起点集合和终点集合是给定的了。发现不存在其他起点和终点匹配的方法使得存在不交路径组，所以我们用 LGV 就能够计算出的就是答案。

而从 (a,1)\to (b,n) 的路径数我们是可以通过组合数来去计算的，就是 \dbinom{n-1+b-a}{b-a}，让后将这个赋值到行列式上，对行列式求值就是答案，时间复杂度为 O(m^3) 瓶颈在行列式求值。

放主函数的代码：

void solve(){
    read(n,m);
    for(int i=1;i<=m;i++){
        read(a[i],b[i]);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            if(a[i]<=b[j]){
                mt[i][j]=getC(n-a[i]+b[j]-1,n-1);
            }else{
                mt[i][j]=0;
            }
        }
    }
    put(HLS::solve());// 就是求行列式的函数。
}

有向图哈密顿路

给你一个 n 个点 m 条边的有向图，让你找到一个 k 个点的路径是的路径上的点互不相同。

我没找到题，问题在于如何让路径上的点互不相同，我们需要有一种在经过重复点的时候就一定不会统计的方法。

根据行列式的性质：若行列式两行相同，行列式的值为 0。

我们考虑给每一个点赋值一个 k 维向量 v，对于一个 k 个点的路径 a_1,a_2,\dots,a_k，若 \det \begin{bmatrix} v_{a_1} \\ v_{a_2} \\ \vdots \\ v_{a_k} \end{bmatrix}=0 的话说明存在重复点，否则不存在重复点，如果我们给 v 随机赋权的话，根据我们前面的说法，错误率是 \dfrac{1}{MOD}。

那么通过上面的方法，我们不需要记录我们所经过的点，只需要进行数据运算就可以了，而对于上面行列式的求值，我们可以通过定义进行。这样的话我们可以通过考虑 DP 进行计算，设 f(i,j,S) 表示考虑了前 i 个点，第 i 个点为 j 的情况下，前 i 行行列式求值选择的排列取值集合为 S 的情况下前 i 行的带符号和。

考虑转移的时候直接枚举边以及这一行选择的排列取值，最终 f(k,v_i,\{1,2,\dots,k\} 的第一个非零的位置 v_i 求实一个可行的终点，让后倒退求出路径即可，时间复杂度 O(mk^2 2^k)，没想到吧和 n 一点关系都没有。

PA2021 Fiolki 2

有一张 n 个点 m 条边的有向无环图。记 f(l, r)\ (k < l \le r \le n) 表示以 1 \sim k 中的点为起点，l \sim r 中的点为终点，最多能够选出多少条路径，使得任意两条路径不存在公共节点。对于 x = 0, 1, \ldots, k，问有多少对 l, r 满足 f(l, r) = x。

只是让我们求不想交的路径耶？我们可以考虑给边随机赋权来完整这个事，让后用 LGV 来进行检验，具体操作就是对于每一个 k<i\le n 维护 1\sim k 到 i 所有路径的权值和，将其看做一个 k 维向量。若 f(l,r)=k，根据 LGV 有就是找到 a_1,a_2,\dots,a_k \in [l,r] 使得这 k 个点对应的向量排成一列构成的矩阵的行列式值不为 0。说人话就是在 [l,r] 找到 k 个线性无关的向量。

依次类推，有 f(l,r)\ge x，就意味着能够在 [l,r] 找到 x 个线性无关的向量，所以 f(l,r) 就是 [l,r] 的每一个点对应的向量所构成线性基的大小。

考虑这个怎么维护，先让我们不可能直接暴力的去维护不然时间复杂度就直接螺旋爆炸上天，但是我们观察性质，对于确定的 r，f(l,r) 的值随 l 的减小而增大，若 f(l,r)\neq f(l-1,r) 那么也就意味着 a_l 与 a_{l+1},\dots a_r 线性无关，我们可以加入线性基中。而现在问题转化为找到这些 l 让后从小到大排序，将相邻两项的差求和就是我们的答案，而我们找 l 可以维护时间戳线性基求得，时间复杂度为 O(mk+nk^2)。

SNCPC2024 最大流

不会真跑网络流吧 www。

其实就是让你找边不交的路径，并且对 k 取 \min。首先这个 \min 这个很难受，我们考虑能不能通过转化把他给去掉，我们可以通过添加个点 0，让后让它向 1 连 k 条边，让后就可以去掉了。

但是 LGV 检验的是点不交，考虑点边转化 Trick，将点转化为边，将边转化为点，具体来时就是每一条边对应一个节点，对于一个点所有入边向出边链接带有随机权值的边（因为题目还是检验），那么 i 点的答案就是等于 i 的所有入边对应向量构成的线性基大小即可。

显然我给你个菊花图就炸掉了，考虑优化。

所有入边向出边连边，对每个边随机赋权，根据 LGV 的说法权值是乘起来的，那这不就是随机线性组合吗？而且我们答案要线性基求得还是线性无关的向量个数，所以对于入边我们只需要保留线性无关的 k 组向量解决即可，这玩意还是线性基，直接做就可以啦。

时间复杂度 O((n+m)k^2)。