LGV引理
特殊形式¶
在一张DAG中，有一组起点 \(A=\{a_1,a_2,\cdots,a_n\}\) 与终点 \(B=\{b_1,b_2,\cdots,b_n\}\)。
设一个矩阵，其中\(e(a_i,b_i)\)表示从点\(a_i\)到点\(b_i\)的所有可行路径数（一般用bfs或组合数求）：
则有定理：\(\det(M)\) 的值是从 \(A\) 到 \(B\) 的所有互不相交路径方案的数量。
等价于：偶数个交点的路径方案数比有奇数个交点的路径方案数多多少个（逆序对）。
https://www.luogu.com.cn/problem/P7736
这个值可以由高斯消元 > 高斯消元求行列式 待完成求出，倒三角方阵斜边上的所有数之积即为det。
感性证明¶
二元，只有两种情况，要么一对一，二对二；要么打交叉。我们考虑打交叉的路径二元组 \(P(a_1,b_2),P(a_2,b_1)\)，不难发现，在交点处，如果把剩下的路径交换，则变为了 \(P(a_1,b_1),P(a_2,b_2)\) 中路径相交的方案。
可以证明，这样的对应关系是双射。那么所有一对一，二对二的方案数减去打交叉的方案数，就是所有不相交路径的方案数。
更复杂一点的情况，更多交点也类似。
多元，设起点为编号\(1\cdots n\)，则终点编号为\([1,n]\)的一个排列，路径相交和该排列的逆序对个数有关，偶数个逆序对加，奇数个逆序对减。
更一般的形式——带边权（即有重边）¶
上面的各边边权为\(1\)。当\(\omega_e \not= 1\)时，定义 \(\omega(P)\) 为一条路径 \(P\) 中每条边权的乘积，即 \(\omega(P)=\prod_{e\in P} w_e\)（可以看作是算上重边时，一条路径的方案数）。
考虑选 \(n\) 条路径将所有 \(A\) 和 \(B\) 一一配对，设其中一种路径组方案为 \(G=(P_1,P_2,\cdots,P_n)\)，则路径 \(P_i=(a_i,b_j)\)，所有的 \(j\) 构成一个 \([1,n]\) 的排列，其逆序对数量记作 \(t(G)\)。
该路径组的总方案数为其所有路径方案之积：\(W(G)=\prod_{i=1}^n \omega(P_i)\)。
那么LGV引理描述为，设一个矩阵，其中 \(e(a,b)\) 为两点之间所有路径 \(P\) 的 \(\omega(P)\) 之和（好吧，加法原理，算出两点间所有可行方案数）
则有：
注：\(G\) 是一个从 \(A\) 到 \(B\) 的不相交路径组（其中一种方案），边不带权时 \(W(G)=1\)。
证明涉及到行列式定义，详见：https://zhuanlan.zhihu.com/p/517819133
卡特兰数？？？的几个意义？ 待完成{: #待完成 .hash}
