LGV 引理学习笔记

前言

这玩意能解决 DAG 上的不相交路径问题

为啥学呢，因为之前做 CF 有个奇怪的题，能用这玩意秒（我还用容斥瞎几把乱搞了半天

正片

\(P\) 是一条路径

\(w(P)\) 表示 \(P\) 这条路径上的边权之积，通常设为 1（目前还没有碰到其他类型的）

\(e(u,v)\) 表示 \(u\) 到 \(v\) 的每一条路径上的 \(w\) 之和，即 \(e(u,v) = \sum w(p)[P:u \rightarrow v]\)

如果 \(w(P)\) 为 1，那 \(e(u,v)\) 就是从 \(u\) 到 \(v\) 的路径数

起点集合 \(A\)，终点集合 \(B\)，都是 \(size\) 为 \(n\) 的点集

设一个矩阵

\[M = \left[\begin{matrix} 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{matrix} \right] \]

那么

\[P_i = [A_i \rightarrow B_i] \\ P = (P_1,P_2,\cdots , P_n) \]

且满足 \(P_i\) 之间两两没有相交点（包括起点和终点） 的方案数就是 \(det(M)\)

证明

尝试理解 wikipedia 上的证明，失败了

问了一下 pb ，他说 大概就是只要有交点就可以在那个交点进行终点的置换，然后容斥一下就刚好消失了

没有线代基础，不是很能理解 /kk

等我水平高一点之后再来填坑吧