【学习笔记】LGV 引理

imily's notebook

2021-03-03

学习笔记

LGV 引理，用来处理有向无环图上的不相交路径计数问题。

$w(Path)$ 表示 $Path$ 这条路径上的边权积，也可以是生成函数，这样就能搞很多事情
$e(u, v)$ 表示 $u$ 到 $v$ 所有路径的 $w(Path)$ 之和
$N(\sigma)$ 表示 $\sigma$ 这个排列的逆序对数
有矩阵 $M$ 和点集 $A$、$B$，$M_{i, j} = e(A_i, B_j)$

$ans = det(M) = \sum\limits_{S : A \rightarrow B} (-1)^{N(\sigma(S))} \prod\limits_{i = 1}^n w(S_i)$

其中 $S$ 这个映射是在枚举 $A$ 到 $B$ 的每个路径组。

感性理解挺容易的，所有相交的路径从排列角度都可以看作在相交的那一刻互换灵魂，会形成逆序对；只要逆序对数 $> 0$，经过类行列式的容斥，这个路径组贡献就是 $0$。

$Gym102978-A$

先不考虑 $a_{R, C} = V$。划一条折线 $i$ 表示分割了 $val_i$ 和 $val_{i + 1}$，共有 $k - 1$ 条线，将每条线向右向下平移一个单位后转化成不相交路径计数，上 LGV。

考虑 $a_{R, C} = V$。诶——也就是说恰好 $V - 1$ 条折线跨过了 $(R, C)$ 西北方向的直线！怎么用 LGV 呢？边积 + 生成函数！把 $(R, C)$ 西北方向的所有路径的 $w()$ 赋为 $z$，答案就是行列式求出的生成函数第 $V - 1$ 项。然而行列式套卷积什么的显然boom，考虑见过的套路——随便什么带进去，最后插回来得到系数。

$Code$

~~好诶又水了一篇~~ 碰到有趣的题目会回来写的啦

upd on 2021.7.22: 补一道 XJOI2817 xza 场 T3！！

操作计数

先只考虑每次下标不同的限制。

设总操作数为 $t$。每个下标 $i$ 需要操作次数为 $d_i = b_i - a_i$。

容斥，枚举不合法操作数 $s$（被分到了相同的下标上），每个下标 $i$ 分到的不合法操作数 $x_i$，贡献是 $(-1)^s \binom{s}{x_1, \cdots, x_n} \binom{t}{s} \binom{2(t - s)}{d_1 - 2x_1, \cdots, d_n - 2x_n} = \prod\limits_{i = 1, \sum x_i = s}^n \frac{ 1 }{ x_i! (d_i - 2x_i)! } (-1)^s s! [2(t - s)]! \binom{t}{s}$，后面这坨关于 $s$ 可以最后处理。

考虑 EGF。设 $f_{k}(x)$ 表示 $d_i = k$ 的 EGF, $f_{k}(x) = \sum \frac{1}{(k - 2i)!} \frac{x^i}{i!}$

现在考虑数互不相等的限制。转化为不相交路径计数，上 LGV，$mat_{i, j} = f_{b_j - a_i}(x)$，带单位根插出多项式（经典操作

相当于两个容斥套起来，正确性显然。

注意这里有个细节就是我们默认序列递增，每次操作是大的下标在前，这样保证同一次操作不会引发可避免的「数相等」事件。因此答案要除以 $2^t$。