LGV 引理
概述
参考 OI Wiki
Lindström–Gessel–Viennot lemma，即 LGV 引理，可以用来处理有向无环图上不相交路径计数等问题。
引理
定义方阵 \(M\)。
结论是：
\[\det(M) = \sum_{S:A\to B} (-1)^{sgn(\sigma(S))} \prod_{i=1}^n \omega(S_i) \]其中 \(S:A\to B\) 表示不相交路径集合。
证明？我不会。鸽掉，不一定补。
标签：路径,相交,lemma,sgn,引理,LGV From： https://www.cnblogs.com/liyixin0514/p/18648738