标签：dots LGC 路径 棋子 rightarrow 引理 sigma vdots

LGV引理

内容（不会证明）

\(\omega(P)\) 表示 P 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 1）（事实上，边权可以为生成函数）

e(u, v) 表示 u 到 v 的 每一条 路径 P 的 $\omega(P) $之和，即 $ e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)$。

起点集合 \(A\)，是有向无环图点集的一个子集，大小为 \(n\)。

终点集合 \(B\)，也是有向无环图点集的一个子集，大小也为 \(n\)。

一组 \(A\rightarrow B\) 的不相交路径 \(S\)：$S_i $是一条从 \(A_i\) 到 \(B_{\sigma(S)_i}\) 的路径（\(\sigma(S)\) 是一个排列），对于任何 \(i\ne j\)，$S_i $和 \(S_j\) 没有公共顶点。

\(t(\sigma)\) 表示排列 \(\sigma\) 的逆序对个数。

\[M = \begin{bmatrix} e(A_1,B_1) & e(A_1,B_2) & \dots &; e(A_1,B_m)\\ e(A_2,B_1) & e(A_2,B_2) & \dots & e(A_2,B_m)\\ \vdots & \vdots & \ddots & \vdots\\ e(A_n,B_1) & e(A_n,B_2) & \dots & e(A_n,B_m) \end{bmatrix} \]

满足

\[\det(M)=\sum_{P:A\rightarrow B}(-1)^{t(\sigma(P))}\prod_{i=1}^nw(P_i) \]

模板题

有一个 \(n\times n\) 的棋盘，左下角为 \((1,1)\)，右上角为 \((n,n)\)，若一个棋子在点 \((x,y)\)，那么走一步只能走到 \((x+1,y)\) 或 \((x,y+1)\)。

现在有 \(m\) 个棋子，第 \(i\) 个棋子一开始放在 \((a_i,1)\)，最终要走到 \((b_i,n)\)。问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过路径上的点互不相交。输出方案数 \(\bmod\ 998244353\) 的值。

两种方案不同当且仅当存在至少一个棋子所经过的点不同。

solution

e可以用组合数简单的算出来，然后我们发现，因为路径没有交，只要逆序对数大于0就没贡献，于是答案就是行列式

标签：dots,LGC,路径,棋子,rightarrow,引理,sigma,vdots
From： https://www.cnblogs.com/zhy114514/p/18028181