LGV引理

发表于 分类于

引言

LGV引理可以用来解决在DAG上不相交路径的计数。

题意

给定一个有向无环图，各 $k$ 个点的集合 $A,B$ 。要求从统计 $n$ 条从 $A_i$ 到 $B_i$ 的路径，每个点至多在一条路径中的方案数 $N$。

LGV引理

记 $e(u,v)$ 为从点 $u$ 到点 $v$ 的路径方案数，则有：

$$
\left | N \right |=\begin{vmatrix}
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{vmatrix}
$$

证明感性理解

$$
|N|=\sum_{p_i\in [1,n],p_i\neq p_j}(-1)^{\sigma(p)}\prod_{i=1}^n e（A_i,B_{p_i})
$$

假如某种方案出现了相交情况，比如从 $A_1$ 到 $B_i$ 与从 $A_2$ 到 $B_j$ 出现了相交，那么将 $B_i$ 与 $B_j$ 交换后，逆序对个数奇偶性改变，由容斥原理一减一加就没了。

于是求个行列式就好了。

$e$ 数组也可以直接DP算出来。

时间复杂度 $O(n^3)$。

例题