OI-wiki 图论专题LGV 引理——用行列式解决 DAG 不相交路径计数问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读Lindström–Gessel–Viennot 引理简称 LGV 引理是 OI / ICPC 竞赛中处理有向无环图DAG不相交路径计数问题的核心工具。它的威力在于一组起点集合到一组终点集合的不相交路径组的带符号计数恰好等于一个由两点间路径权值和构成的矩阵的行列式。阅读本文后你将掌握 LGV 引理的严格数学定义、行列式证明思路以及 CF348D Turtles 与 HDU 5852 两道经典例题的完整推导与 参考实现、参考实现能够独立将棋盘/网格上两两不相交路径计数类问题转化为行列式计算。本文主体内容源自 OI-wiki 图论模块的 LGV 引理文档并结合作者仓库中的配套源码与测试用例进行深度展开。一、前置知识与适用前提LGV 引理并不是一个普适的计数魔法它有一项硬性前提LGV 引理仅适用于有向无环图DAG。这一点至关重要引理证明中大量使用路径组交换后缀后符号改变的配对抵消论证这要求图中不存在环否则路径的定义与配对关系都会失效。在深入学习之前建议先熟悉以下前置知识均在当前仓库中有对应文档图论相关概念 的基础部分路径、排列、逆序对等矩阵基础矩阵乘法、行列式展开的定义高斯消元求行列式在点数较多时计算行列式的标准算法。二、核心定义路径权、路径和与不相交路径组设 $G$ 是一个有向无环图定义如下几个量1. 路径权值 $\omega(P)$$\omega(P)$ 表示路径 $P$ 上所有边的边权之积。做路径计数时只需把所有边权都设为 $1$此时 $\omega(P) \equiv 1$一条路径的权值就是 $1$事实上边权还可以是生成函数这为带权统计提供了极大的灵活性例如给边权赋 $x$ 的幂次以统计长度分布。2. 路径权值和 $e(u, v)$$e(u, v)$ 表示从 $u$ 到 $v$ 的每一条路径 $P$ 的 $\omega(P)$ 之和即$$e(u, v)\sum_{P:u\rightarrow v}\omega(P)$$当边权全为 $1$ 时$e(u,v)$ 就是 $u$ 到 $v$ 的路径条数。可以直观地理解为加权路径计数。3. 起点集合与终点集合起点集合 $A{A_1,A_2,\dots,A_n}$DAG 点集的一个大小为 $n$ 的子集终点集合 $B{B_1,B_2,\dots,B_n}$DAG 点集的一个同样大小为 $n$ 的子集。4. 不相交路径组 $S$一组 $A\rightarrow B$ 的不相交路径 $S$ 满足$S_i$ 是一条从 $A_i$ 到 $B_{\sigma(S)_i}$ 的路径其中 $\sigma(S)$ 是一个排列即路径终点与起点之间是一个双射对于任何 $i\ne j$$S_i$ 和 $S_j$没有公共顶点即两两顶点不相交。5. 排列的逆序对数 $t(\sigma)$$t(\sigma)$ 表示排列 $\sigma$ 的逆序对个数。它决定了求和项前的符号 $(-1)^{t(\sigma)}$这是行列式展开中天然出现的因子。三、LGV 引理行列式等于不相交路径组的带符号和3.1 引理陈述构造 $n\times n$ 矩阵 $M$其元素为$$ M \begin{bmatrix} e(A_1,B_1)e(A_1,B_2)\cdotse(A_1,B_n)\ e(A_2,B_1)e(A_2,B_2)\cdotse(A_2,B_n)\ \vdots\vdots\ddots\vdots\ e(A_n,B_1)e(A_n,B_2)\cdotse(A_n,B_n) \end{bmatrix} $$则 LGV 引理断言$$ \det(M)\sum_{S:A\rightarrow B}(-1)^{t(\sigma(S))}\prod_{i1}^n \omega(S_i) $$其中 $\sum\limits_{S:A\rightarrow B}$ 遍历满足上文要求的每一组$A\rightarrow B$ 不相交路径 $S$。解读行列式的值等于所有不相交路径组的带符号权值之和。也就是说尽管 $e(u,v)$ 里混入了大量会相交的路径行列式的展开与符号配对会自动把这些相交路径组全部抵消只留下不相交的那些。3.2 证明思路第一步按行列式定义展开。由行列式定义$$ \begin{align} \det(M)\sum_{\sigma}(-1)^{t(\sigma)}\prod_{i1}^n e(a_i,b_{\sigma(i)})\ \sum_{\sigma}(-1)^{t(\sigma)}\prod_{i1}^n \sum_{P:a_i\to b_{\sigma(i)}} \omega(P) \end{align} $$观察到 $\prod\limits_{i1}^n \sum\limits_{P:a_i\to b_{\sigma(i)}} \omega(P)$ 实际上是所有排列为 $\sigma$ 的路径组 $P$的 $\omega(P)$ 之和于是$$ \begin{align} \sum_{\sigma}(-1)^{t(\sigma)}\prod_{i1}^n \sum_{P:a_i\to b_{\sigma(i)}} \omega(P)\ \sum_{\sigma}(-1)^{t(\sigma)}\sum_{P\sigma}\omega(P)\ \sum_{P:A\to B}(-1)^{t(\sigma)}\prod_{i1}^n \omega(P_i) \end{align} $$此处 $P$ 为任意路径组允许相交。第二步把路径组分为不相交$U$与相交$V$两类。$$ \begin{align} \sum_{P:A\to B}(-1)^{t(\sigma)}\prod_{i1}^n \omega(P_i)\ \sum_{U:A\to B}(-1)^{t(U)}\prod_{i1}^n \omega(U_i)\sum_{V:A\to B}(-1)^{t(V)}\prod_{i1}^n \omega(V_i) \end{align} $$第三步关键配对抵消——相交路径组的贡献为 $0$。设相交路径组 $P$ 中存在两条路径在顶点 $u$ 相交$$P_i:a_1 \to u \to b_1,\qquad P_j:a_2 \to u \to b_2$$则必然存在与之配对的另一个相交路径组 $P$把这两条路径在 $u$ 之后的后缀交换即$$P_ia_1\to u\to b_2,\qquad P_ja_2\to u\to b_1$$$P$ 的其余路径与 $P$ 完全相同。由于只交换了后缀边权乘积不变故 $\omega(P)\omega(P)$交换两条路径的终点相当于交换排列中的两个元素逆序对奇偶性改变故 $t(P)t(P)\pm 1$。因此 $P$ 与 $P$ 在求和 $\sum\limits_{V:A\to B}(-1)^{t(\sigma)}\prod\limits_{i1}^n \omega(V_i)$ 中符号相反、权值相等恰好成对抵消。于是$$\sum_{V:A\to B}(-1)^{t(\sigma)}\prod_{i1}^n \omega(V_i)0$$第四步结论。$$ \det(M)\sum_{U:A\to B}(-1)^{t(U)}\prod_{i1}^n \omega(U_i) $$证毕。该证明思路与 知乎 - LGV 引理证明 一致原文出处见 OI-wiki lgv 文档 的参考资料脚注。证明的关键启示LGV 引理的实用性建立在相交路径可两两配对抵消之上。这解释了为什么在实际应用中我们常常只需关心若路径不相交则终点排列必然唯一确定的情形——此时符号项可以完全忽略答案就是行列式本身详见第四节例题 2。四、经典例题实战4.1 例 1CF348D Turtles——2×2 行列式的直接应用题目Codeforces 348D有一个 $n\times m$ 的格点棋盘某些格子可走、某些不可走。一只海龟从 $(x,y)$ 只能走到 $(x1,y)$ 或 $(x,y1)$求海龟从 $(1,1)$ 到 $(n,m)$ 的不相交路径数对 $10^97$ 取模的结果。数据范围 $2\le n,m\le 3000$。分析这是 LGV 引理最直接的入门应用。观察所有合法路径从 $(1,1)$ 出发的第一步必然经过 $A{(1,2),(2,1)}$ 中的某一点到达终点前的最后一步必然经过 $B{(n-1,m),(n,m-1)}$ 中的某一点。于是起点集合与终点集合立即确定为$$A{a_1(1,2),;a_2(2,1)},\qquad B{b_1(n-1,m),;b_2(n,m-1)}$$套用 LGV 引理$n2$ 情形行列式是一个 $2\times 2$ 行列式$$ \begin{vmatrix} f(a_1, b_1) f(a_1, b_2) \ f(a_2, b_1) f(a_2, b_2) \end{vmatrix} f(a_1, b_1)\times f(a_2, b_2) - f(a_1, b_2)\times f(a_2, b_1) $$其中 $f(a,b)$ 为图上 $a\rightarrow b$ 的路径数。带有障碍格点的路径计数可以直接做 $O(nm)$ 的 DP 求得因此总复杂度 $O(nm)$。仓库配套实现位于 docs/graph/code/lgv/lgv_2.cpp其关键结构为int f(int x1, int y1, int x2, int y2) { memset(dp, 0, sizeof dp); dp[x1][y1] board[x1][y1] .; for (int i 1; i x2; i) { for (int j 1; j y2; j) { if (board[i][j] #) continue; // 障碍格跳过 dp[i][j] (dp[i][j] dp[i - 1][j]) % MOD; // 从上方转移 dp[i][j] (dp[i][j] dp[i][j - 1]) % MOD; // 从左方转移 } } return dp[x2][y2] % MOD; }主程序对四组点对分别调用 $f$再计算行列式并取模ll f11 f(1, 2, n - 1, m); ll f12 f(1, 2, n, m - 1); ll f21 f(2, 1, n - 1, m); ll f22 f(2, 1, n, m - 1); ll ans ((f11 * f22) % MOD - (f12 * f21) % MOD MOD) % MOD;实现要点从源码结构可以归纳棋盘输入时给每行前拼接一个空格字符board[i] board[i]使得下标从 $1$ 开始避免越界判断DP 中先判#障碍、再累加上方与左方来源保证dp值始终为模意义下的路径数减法结果 MOD后再取模避免出现负数。配套测试数据在 docs/graph/examples/lgv/lgv_2.in 与 docs/graph/examples/lgv/lgv_2.ans// 输入4×5 棋盘中间两行有障碍 4 5 ..... .###. .###. ..... // 期望输出 1从代码与样例可以验证即使存在障碍格只要把 $f$ 的 DP 做好、代入 $2\times2$ 行列式就能得到正确的不相交路径数。4.2 例 2HDU 5852 Intersection is not allowed!——高斯消元求大行列式题目HDU 5852有一个 $n\times n$ 棋盘棋子从 $(x,y)$ 只能走到 $(x,y1)$ 或 $(x1,y)$。有 $k$ 个棋子第 $i$ 个棋子一开始放在 $(1,a_i)$最终要到 $(n,b_i)$路径要两两不相交求方案数对 $10^97$ 取模。数据范围$1\le n\le 10^5$$1\le k\le 100$并保证 $1\le a_1a_2\dotsa_k\le n$$1\le b_1b_2\dotsb_k\le n$。分析符号项消失的巧妙之处观察到起点序列 $a_i$ 与终点序列 $b_i$ 都是严格递增的。在只能向下/向右走的棋盘上如果两条路径不相交则第 $i$ 个起点必然对应第 $i$ 个终点即 $\sigma(S)_ii$恒等排列。此时 $t(\sigma)0$LGV 引理中的符号问题完全消失答案就是行列式本身。组合数求 $e$从 $(1,a_i)$ 到 $(n,b_j)$ 需要向右走 $b_j-a_i$ 步、向下走 $n-1$ 步总共 $n-1b_j-a_i$ 步中选择 $n-1$ 步向下因此$$e(A_i, B_j)\binom{n-1b_j-a_i}{n-1}$$行列式计算$k\le 100$直接使用高斯消元求行列式即可。复杂度为 $O(nk(k^2 \log p))$其中 $\log p$ 是求逆元的复杂度$n$ 用于预处理阶乘$k^2$ 是高斯消元主循环$\log p$ 是每次求逆的快速幂代价。仓库配套实现位于 docs/graph/code/lgv/lgv_1.cpp核心流程如下1预处理阶乘与组合数int qpow(int x, int y) { // 快速幂用于求逆元 int out 1; while (y) { if (y 1) out (ll)out * x % mod; x (ll)x * x % mod; y 1; } return out; } int c(int x, int y) { // 组合数 C(x, y) mod (1e97) return (ll)fact[x] * qpow(fact[y], mod - 2) % mod * qpow(fact[x - y], mod - 2) % mod; }fact[0..2N]在主函数中先行递推fact[i] fact[i-1] * i % mod。由于模数 $10^97$ 是素数可用费马小定理$a^{p-2}$ 为 $a$ 的逆元求组合数。2构造 LGV 矩阵for (int i 1; i k; i) { for (int j 1; j k; j) { if (a[i] b[j]) m[i][j] c(b[j] - a[i] n - 1, n - 1); else m[i][j] 0; // 起点在终点下方路径数为 0 } }注意a[i] b[j]时矩阵元素直接置 $0$向左上方向无法到达这是网格图上 $e(A_i,B_j)$ 的边界条件。3高斯消元化为上三角并累乘对角线for (int i 1; i k; i) { if (!m[i][i]) { // 主元为 0寻找下方非零行交换 for (int j i 1; j k; j) { if (m[j][i]) { std::swap(m[i], m[j]); break; } } } if (!m[i][i]) continue; int inv qpow(m[i][i], mod - 2); // 主元逆元 for (int j i 1; j k; j) { if (!m[j][i]) continue; int mul (ll)m[j][i] * inv % mod; for (int p i; p k; p) m[j][p] (m[j][p] - (ll)m[i][p] * mul % mod mod) % mod; } } int ans 1; for (int i 1; i k; i) ans (ll)ans * m[i][i] % mod; // 对角线乘积实现细节源码可验证消元过程中所有运算都在模 $10^97$ 下进行使用long long承接乘法避免溢出换行操作会改变行列式符号但本题最终答案为正数代码通过消元后直接累乘对角线得到行列式的绝对值——实际上本题矩阵可证其行列式非负故实现中未额外处理换行符号每次减法后 mod再取模保证中间值非负。配套测试数据在 docs/graph/examples/lgv/lgv_1.in 与 docs/graph/examples/lgv/lgv_1.ans// 输入T1 组n5k2起点 (1,1)(1,2)终点 (5,3)(5,4) 1 5 2 1 2 3 4 // 期望输出 50五、方法论总结何时用 LGV、怎么用5.1 适用特征识别结合两道例题可以总结出 LGV 引理的典型应用模式计数对象是多起点 → 多终点、路径两两不相交的方案数图必须是有向无环图网格棋盘天然满足需要能高效计算任意两点间的路径权值和 $e(u,v)$计数时用 DP / 组合数带权时用生成函数若能论证不相交 ⟹ 终点排列唯一则答案就是行列式本身无需处理符号项——这是竞赛中最常见的形态。5.2 通用解题框架步骤操作参考实现1. 选点确定起点集合 $A$、终点集合 $B$通常由题目结构直接给出或由必经点确定例 1$A{(1,2),(2,1)}$2. 求 $e$计算每对 $(A_i,B_j)$ 的路径权值和例 2组合数公式3. 构造矩阵填 $k\times k$ 矩阵 $M_{ij}e(A_i,B_j)$lgv_1.cpp4. 算行列式小规模直接展开$k$ 大时用高斯消元取模例 2 的消元循环5. 处理符号排列唯一则忽略否则需要带符号求和例 1 的 $2\times2$ 展开5.3 常见误区提醒忘记 DAG 前提把 LGV 引理套在含环图上会得到错误结果配对抵消论证依赖无环性忽略符号项只有当不相交 ⟹ 排列唯一或能逐个枚举排列时才可忽略 $(-1)^{t(\sigma)}$组合数越界例 2 中 $n$ 可达 $10^5$阶乘要预处理到 $2N$ 的量级$N\times2200005$见源码constexpr int N 100005否则 $b_j-a_in-1$ 可能超过预处理的阶乘范围。参考资料OI-wikiLGV 引理本文主体来源例 1 参考实现CF348D Turtles例 2 参考实现HDU 5852例 1 测试数据 与 答案例 2 测试数据 与 答案证明思路来源知乎 - LGV 引理证明【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
OI-wiki 图论专题：LGV 引理——用行列式解决 DAG 不相交路径计数问题
OI-wiki 图论专题LGV 引理——用行列式解决 DAG 不相交路径计数问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读Lindström–Gessel–Viennot 引理简称 LGV 引理是 OI / ICPC 竞赛中处理有向无环图DAG不相交路径计数问题的核心工具。它的威力在于一组起点集合到一组终点集合的不相交路径组的带符号计数恰好等于一个由两点间路径权值和构成的矩阵的行列式。阅读本文后你将掌握 LGV 引理的严格数学定义、行列式证明思路以及 CF348D Turtles 与 HDU 5852 两道经典例题的完整推导与 参考实现、参考实现能够独立将棋盘/网格上两两不相交路径计数类问题转化为行列式计算。本文主体内容源自 OI-wiki 图论模块的 LGV 引理文档并结合作者仓库中的配套源码与测试用例进行深度展开。一、前置知识与适用前提LGV 引理并不是一个普适的计数魔法它有一项硬性前提LGV 引理仅适用于有向无环图DAG。这一点至关重要引理证明中大量使用路径组交换后缀后符号改变的配对抵消论证这要求图中不存在环否则路径的定义与配对关系都会失效。在深入学习之前建议先熟悉以下前置知识均在当前仓库中有对应文档图论相关概念 的基础部分路径、排列、逆序对等矩阵基础矩阵乘法、行列式展开的定义高斯消元求行列式在点数较多时计算行列式的标准算法。二、核心定义路径权、路径和与不相交路径组设 $G$ 是一个有向无环图定义如下几个量1. 路径权值 $\omega(P)$$\omega(P)$ 表示路径 $P$ 上所有边的边权之积。做路径计数时只需把所有边权都设为 $1$此时 $\omega(P) \equiv 1$一条路径的权值就是 $1$事实上边权还可以是生成函数这为带权统计提供了极大的灵活性例如给边权赋 $x$ 的幂次以统计长度分布。2. 路径权值和 $e(u, v)$$e(u, v)$ 表示从 $u$ 到 $v$ 的每一条路径 $P$ 的 $\omega(P)$ 之和即$$e(u, v)\sum_{P:u\rightarrow v}\omega(P)$$当边权全为 $1$ 时$e(u,v)$ 就是 $u$ 到 $v$ 的路径条数。可以直观地理解为加权路径计数。3. 起点集合与终点集合起点集合 $A{A_1,A_2,\dots,A_n}$DAG 点集的一个大小为 $n$ 的子集终点集合 $B{B_1,B_2,\dots,B_n}$DAG 点集的一个同样大小为 $n$ 的子集。4. 不相交路径组 $S$一组 $A\rightarrow B$ 的不相交路径 $S$ 满足$S_i$ 是一条从 $A_i$ 到 $B_{\sigma(S)_i}$ 的路径其中 $\sigma(S)$ 是一个排列即路径终点与起点之间是一个双射对于任何 $i\ne j$$S_i$ 和 $S_j$没有公共顶点即两两顶点不相交。5. 排列的逆序对数 $t(\sigma)$$t(\sigma)$ 表示排列 $\sigma$ 的逆序对个数。它决定了求和项前的符号 $(-1)^{t(\sigma)}$这是行列式展开中天然出现的因子。三、LGV 引理行列式等于不相交路径组的带符号和3.1 引理陈述构造 $n\times n$ 矩阵 $M$其元素为$$ M \begin{bmatrix} e(A_1,B_1)e(A_1,B_2)\cdotse(A_1,B_n)\ e(A_2,B_1)e(A_2,B_2)\cdotse(A_2,B_n)\ \vdots\vdots\ddots\vdots\ e(A_n,B_1)e(A_n,B_2)\cdotse(A_n,B_n) \end{bmatrix} $$则 LGV 引理断言$$ \det(M)\sum_{S:A\rightarrow B}(-1)^{t(\sigma(S))}\prod_{i1}^n \omega(S_i) $$其中 $\sum\limits_{S:A\rightarrow B}$ 遍历满足上文要求的每一组$A\rightarrow B$ 不相交路径 $S$。解读行列式的值等于所有不相交路径组的带符号权值之和。也就是说尽管 $e(u,v)$ 里混入了大量会相交的路径行列式的展开与符号配对会自动把这些相交路径组全部抵消只留下不相交的那些。3.2 证明思路第一步按行列式定义展开。由行列式定义$$ \begin{align} \det(M)\sum_{\sigma}(-1)^{t(\sigma)}\prod_{i1}^n e(a_i,b_{\sigma(i)})\ \sum_{\sigma}(-1)^{t(\sigma)}\prod_{i1}^n \sum_{P:a_i\to b_{\sigma(i)}} \omega(P) \end{align} $$观察到 $\prod\limits_{i1}^n \sum\limits_{P:a_i\to b_{\sigma(i)}} \omega(P)$ 实际上是所有排列为 $\sigma$ 的路径组 $P$的 $\omega(P)$ 之和于是$$ \begin{align} \sum_{\sigma}(-1)^{t(\sigma)}\prod_{i1}^n \sum_{P:a_i\to b_{\sigma(i)}} \omega(P)\ \sum_{\sigma}(-1)^{t(\sigma)}\sum_{P\sigma}\omega(P)\ \sum_{P:A\to B}(-1)^{t(\sigma)}\prod_{i1}^n \omega(P_i) \end{align} $$此处 $P$ 为任意路径组允许相交。第二步把路径组分为不相交$U$与相交$V$两类。$$ \begin{align} \sum_{P:A\to B}(-1)^{t(\sigma)}\prod_{i1}^n \omega(P_i)\ \sum_{U:A\to B}(-1)^{t(U)}\prod_{i1}^n \omega(U_i)\sum_{V:A\to B}(-1)^{t(V)}\prod_{i1}^n \omega(V_i) \end{align} $$第三步关键配对抵消——相交路径组的贡献为 $0$。设相交路径组 $P$ 中存在两条路径在顶点 $u$ 相交$$P_i:a_1 \to u \to b_1,\qquad P_j:a_2 \to u \to b_2$$则必然存在与之配对的另一个相交路径组 $P$把这两条路径在 $u$ 之后的后缀交换即$$P_ia_1\to u\to b_2,\qquad P_ja_2\to u\to b_1$$$P$ 的其余路径与 $P$ 完全相同。由于只交换了后缀边权乘积不变故 $\omega(P)\omega(P)$交换两条路径的终点相当于交换排列中的两个元素逆序对奇偶性改变故 $t(P)t(P)\pm 1$。因此 $P$ 与 $P$ 在求和 $\sum\limits_{V:A\to B}(-1)^{t(\sigma)}\prod\limits_{i1}^n \omega(V_i)$ 中符号相反、权值相等恰好成对抵消。于是$$\sum_{V:A\to B}(-1)^{t(\sigma)}\prod_{i1}^n \omega(V_i)0$$第四步结论。$$ \det(M)\sum_{U:A\to B}(-1)^{t(U)}\prod_{i1}^n \omega(U_i) $$证毕。该证明思路与 知乎 - LGV 引理证明 一致原文出处见 OI-wiki lgv 文档 的参考资料脚注。证明的关键启示LGV 引理的实用性建立在相交路径可两两配对抵消之上。这解释了为什么在实际应用中我们常常只需关心若路径不相交则终点排列必然唯一确定的情形——此时符号项可以完全忽略答案就是行列式本身详见第四节例题 2。四、经典例题实战4.1 例 1CF348D Turtles——2×2 行列式的直接应用题目Codeforces 348D有一个 $n\times m$ 的格点棋盘某些格子可走、某些不可走。一只海龟从 $(x,y)$ 只能走到 $(x1,y)$ 或 $(x,y1)$求海龟从 $(1,1)$ 到 $(n,m)$ 的不相交路径数对 $10^97$ 取模的结果。数据范围 $2\le n,m\le 3000$。分析这是 LGV 引理最直接的入门应用。观察所有合法路径从 $(1,1)$ 出发的第一步必然经过 $A{(1,2),(2,1)}$ 中的某一点到达终点前的最后一步必然经过 $B{(n-1,m),(n,m-1)}$ 中的某一点。于是起点集合与终点集合立即确定为$$A{a_1(1,2),;a_2(2,1)},\qquad B{b_1(n-1,m),;b_2(n,m-1)}$$套用 LGV 引理$n2$ 情形行列式是一个 $2\times 2$ 行列式$$ \begin{vmatrix} f(a_1, b_1) f(a_1, b_2) \ f(a_2, b_1) f(a_2, b_2) \end{vmatrix} f(a_1, b_1)\times f(a_2, b_2) - f(a_1, b_2)\times f(a_2, b_1) $$其中 $f(a,b)$ 为图上 $a\rightarrow b$ 的路径数。带有障碍格点的路径计数可以直接做 $O(nm)$ 的 DP 求得因此总复杂度 $O(nm)$。仓库配套实现位于 docs/graph/code/lgv/lgv_2.cpp其关键结构为int f(int x1, int y1, int x2, int y2) { memset(dp, 0, sizeof dp); dp[x1][y1] board[x1][y1] .; for (int i 1; i x2; i) { for (int j 1; j y2; j) { if (board[i][j] #) continue; // 障碍格跳过 dp[i][j] (dp[i][j] dp[i - 1][j]) % MOD; // 从上方转移 dp[i][j] (dp[i][j] dp[i][j - 1]) % MOD; // 从左方转移 } } return dp[x2][y2] % MOD; }主程序对四组点对分别调用 $f$再计算行列式并取模ll f11 f(1, 2, n - 1, m); ll f12 f(1, 2, n, m - 1); ll f21 f(2, 1, n - 1, m); ll f22 f(2, 1, n, m - 1); ll ans ((f11 * f22) % MOD - (f12 * f21) % MOD MOD) % MOD;实现要点从源码结构可以归纳棋盘输入时给每行前拼接一个空格字符board[i] board[i]使得下标从 $1$ 开始避免越界判断DP 中先判#障碍、再累加上方与左方来源保证dp值始终为模意义下的路径数减法结果 MOD后再取模避免出现负数。配套测试数据在 docs/graph/examples/lgv/lgv_2.in 与 docs/graph/examples/lgv/lgv_2.ans// 输入4×5 棋盘中间两行有障碍 4 5 ..... .###. .###. ..... // 期望输出 1从代码与样例可以验证即使存在障碍格只要把 $f$ 的 DP 做好、代入 $2\times2$ 行列式就能得到正确的不相交路径数。4.2 例 2HDU 5852 Intersection is not allowed!——高斯消元求大行列式题目HDU 5852有一个 $n\times n$ 棋盘棋子从 $(x,y)$ 只能走到 $(x,y1)$ 或 $(x1,y)$。有 $k$ 个棋子第 $i$ 个棋子一开始放在 $(1,a_i)$最终要到 $(n,b_i)$路径要两两不相交求方案数对 $10^97$ 取模。数据范围$1\le n\le 10^5$$1\le k\le 100$并保证 $1\le a_1a_2\dotsa_k\le n$$1\le b_1b_2\dotsb_k\le n$。分析符号项消失的巧妙之处观察到起点序列 $a_i$ 与终点序列 $b_i$ 都是严格递增的。在只能向下/向右走的棋盘上如果两条路径不相交则第 $i$ 个起点必然对应第 $i$ 个终点即 $\sigma(S)_ii$恒等排列。此时 $t(\sigma)0$LGV 引理中的符号问题完全消失答案就是行列式本身。组合数求 $e$从 $(1,a_i)$ 到 $(n,b_j)$ 需要向右走 $b_j-a_i$ 步、向下走 $n-1$ 步总共 $n-1b_j-a_i$ 步中选择 $n-1$ 步向下因此$$e(A_i, B_j)\binom{n-1b_j-a_i}{n-1}$$行列式计算$k\le 100$直接使用高斯消元求行列式即可。复杂度为 $O(nk(k^2 \log p))$其中 $\log p$ 是求逆元的复杂度$n$ 用于预处理阶乘$k^2$ 是高斯消元主循环$\log p$ 是每次求逆的快速幂代价。仓库配套实现位于 docs/graph/code/lgv/lgv_1.cpp核心流程如下1预处理阶乘与组合数int qpow(int x, int y) { // 快速幂用于求逆元 int out 1; while (y) { if (y 1) out (ll)out * x % mod; x (ll)x * x % mod; y 1; } return out; } int c(int x, int y) { // 组合数 C(x, y) mod (1e97) return (ll)fact[x] * qpow(fact[y], mod - 2) % mod * qpow(fact[x - y], mod - 2) % mod; }fact[0..2N]在主函数中先行递推fact[i] fact[i-1] * i % mod。由于模数 $10^97$ 是素数可用费马小定理$a^{p-2}$ 为 $a$ 的逆元求组合数。2构造 LGV 矩阵for (int i 1; i k; i) { for (int j 1; j k; j) { if (a[i] b[j]) m[i][j] c(b[j] - a[i] n - 1, n - 1); else m[i][j] 0; // 起点在终点下方路径数为 0 } }注意a[i] b[j]时矩阵元素直接置 $0$向左上方向无法到达这是网格图上 $e(A_i,B_j)$ 的边界条件。3高斯消元化为上三角并累乘对角线for (int i 1; i k; i) { if (!m[i][i]) { // 主元为 0寻找下方非零行交换 for (int j i 1; j k; j) { if (m[j][i]) { std::swap(m[i], m[j]); break; } } } if (!m[i][i]) continue; int inv qpow(m[i][i], mod - 2); // 主元逆元 for (int j i 1; j k; j) { if (!m[j][i]) continue; int mul (ll)m[j][i] * inv % mod; for (int p i; p k; p) m[j][p] (m[j][p] - (ll)m[i][p] * mul % mod mod) % mod; } } int ans 1; for (int i 1; i k; i) ans (ll)ans * m[i][i] % mod; // 对角线乘积实现细节源码可验证消元过程中所有运算都在模 $10^97$ 下进行使用long long承接乘法避免溢出换行操作会改变行列式符号但本题最终答案为正数代码通过消元后直接累乘对角线得到行列式的绝对值——实际上本题矩阵可证其行列式非负故实现中未额外处理换行符号每次减法后 mod再取模保证中间值非负。配套测试数据在 docs/graph/examples/lgv/lgv_1.in 与 docs/graph/examples/lgv/lgv_1.ans// 输入T1 组n5k2起点 (1,1)(1,2)终点 (5,3)(5,4) 1 5 2 1 2 3 4 // 期望输出 50五、方法论总结何时用 LGV、怎么用5.1 适用特征识别结合两道例题可以总结出 LGV 引理的典型应用模式计数对象是多起点 → 多终点、路径两两不相交的方案数图必须是有向无环图网格棋盘天然满足需要能高效计算任意两点间的路径权值和 $e(u,v)$计数时用 DP / 组合数带权时用生成函数若能论证不相交 ⟹ 终点排列唯一则答案就是行列式本身无需处理符号项——这是竞赛中最常见的形态。5.2 通用解题框架步骤操作参考实现1. 选点确定起点集合 $A$、终点集合 $B$通常由题目结构直接给出或由必经点确定例 1$A{(1,2),(2,1)}$2. 求 $e$计算每对 $(A_i,B_j)$ 的路径权值和例 2组合数公式3. 构造矩阵填 $k\times k$ 矩阵 $M_{ij}e(A_i,B_j)$lgv_1.cpp4. 算行列式小规模直接展开$k$ 大时用高斯消元取模例 2 的消元循环5. 处理符号排列唯一则忽略否则需要带符号求和例 1 的 $2\times2$ 展开5.3 常见误区提醒忘记 DAG 前提把 LGV 引理套在含环图上会得到错误结果配对抵消论证依赖无环性忽略符号项只有当不相交 ⟹ 排列唯一或能逐个枚举排列时才可忽略 $(-1)^{t(\sigma)}$组合数越界例 2 中 $n$ 可达 $10^5$阶乘要预处理到 $2N$ 的量级$N\times2200005$见源码constexpr int N 100005否则 $b_j-a_in-1$ 可能超过预处理的阶乘范围。参考资料OI-wikiLGV 引理本文主体来源例 1 参考实现CF348D Turtles例 2 参考实现HDU 5852例 1 测试数据 与 答案例 2 测试数据 与 答案证明思路来源知乎 - LGV 引理证明【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
