LGV引理
定义
- $G$ 是一个有向无环图
- 起点 $A=\lbrace a_1,a_2,\cdots,a_n\rbrace$，终点 $B=\lbrace b_1,b_2,\cdots,b_n\rbrace$
- 每条边有边权 $w_e$
- 对于一个有向路径 $P$，定义 $\omega(P)$ 为路径上所有边权的积
- 对于任意顶点 $a,b$，定义 $e(a,b)=\sum_{P:a\rightarrow b}\omega(P)$
设矩阵
从 $A$ 到 $B$ 的不相交路径 $P=(P_1,P_2,\cdots,P_n)$，$P_i$ 表示从 $a_i$ 到 $b_{\sigma(i)}$，其中 $\sigma$ 表示一个排列，并且满足 $i\neq j$，$P_i$ 与 $P_j$ 没有交点，记 $\sigma(P)$ 表示 $P$ 对应的排列
$LGV$ 引理说明， $M$ 的行列式是所有从 $A$ 到 $B$ 的不相交路径 $P=(P_1,P_2,\cdots,P_n)$ 的带符号和，其中符号指 $\sigma(P)$ 的逆序数的奇偶性，记为 $sign(\sigma(P))$
应用
例题
简要题意：有一个 $n\times n$ 的棋盘，左下角为 $(1,1)$，右上角为 $(n,n)$，棋子只能向右或者向上走，现在有 $m$ 个棋子，第 $i$ 个棋子一开始放在 $(a_i,1)$，要走到 $(b_i,n)$，问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过的路径互不相交，方案数对 $998244353$ 取模
$n\le 10^6,m\le 100$
简要题解：考虑 $LGV$ 引理构造矩阵 $A_{i,j}=\binom{b_j-a_i+n-1}{n-1}$，因为只有当 $a_i$ 对应的 $b_{\sigma(i)}$ 为 $b_i$ 时才可能有解，容易得到方案数即为 $det(A)$，高斯消元求解行列式即可，时间复杂度 $O(n+m^3)$
简要题意：有一张网格图，现在有 $n$ 个棋子分别要从 $(0,a_i)$ 走到 $(i,0)$，棋子只能向下或者向右走，问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过的路径互不相交，方案数对 $998244353$ 取模
$n\le 5\times 10^5$
简要题解：我们考虑 $LGV$ 引理，构造矩阵 $A_{i,j}=\binom{a_i+j}{j}=\frac{(a_i+j)!}{a_i!j!}$，然后可以将矩阵通过初等变换变成范德蒙德矩阵，利用卷积求行列式