LGV

这个东西一般用来求 DAG 中从初始点集合 \(S\) 到终止点集合 \(T\) 的有符号不相交路径方案数（不相交指的是点不会同时出现在两个路径中），\(n=|S|=|T|\)。 设 \(P(w)\) 表示路径 \(w\) 上的边权的乘积，\(e(s,t)\) 表示 \(\sum_{w:s\to t ......

题目描述 这是一道模板题。 有一个 \(n\times n\) 的棋盘，左下角为 \((1,1)\)，右上角为 \((n,n)\)，若一个棋子在点 \((x,y)\)，那么走一步只能走到 \((x+1,y)\) 或 \((x,y+1)\)。 现在有 \(m\) 个棋子，第 \(i\) 个棋子一开始放 ......

由于是看 oi-wiki 学的，内容基本是搬过来的。 小前提： LGV 引理仅适用于有向无环图。 定义 \(\omega(P)\) 表示 \(P\) 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 \(1\)）（事实上，边权可以为生成函数） \(e(u,v)\) 表示从 \(u\) 到 ......

归类为线性代数、图论。证明都是神仙，特别是名字带“理”的，不证了。 ## 行列式 ### 定义 行列式（Determinant）是对 $n$ 阶方阵 $A$ 定义的，是一个标量。$A$ 的 $n$ 阶行列式 $det(A)$ 或 $|A|$ 定义如下： $$det(A)=\sum_p(-1)^{\m ......

# LGV引理 定义 $A$ 是起点集合 $\{a_1,a_2,...,a_n\}$ 。 $B$ 是终点集合 $\{b_1,b_2,...,b_n\}$。 定义 $\omega(P)$ 为路径 $P$ 每一条边权值的乘积，即 ： $$ \omega(P) = \prod_{e \in P}w_e $ ......

令$ w(P) $表示路径 $ P$ 的所有边权之积，$e(u,v)$ 表示所有 $u$ 到 $v$ 的路径 $w(P)$ 之和，令： $$ M= \begin{bmatrix} e(A_1,B_1) \quad e(A_1,B_2) \quad ... \quad e(A_1,B_n) \ e(A ......