NOI 2021 D1T2 题解

ix35 · 2021-07-27 09:43:19 · 题解

LGV 引理模板。

大部分 LGV 题的模型中有一个特别的性质：符合要求的匹配只有一组，因此按照匹配的顺序列矩阵求出的就是不交路径数量。

从本题的得分来看，也许有很多人因此并没有真正理解 LGV 原本的描述：

有向无环图 G 中，有点 a_1,\ldots,a_n 和 b_1,\ldots,b_n，定义路径组为 n 条 a_i\to b_j 的路径，这些路径不交，这 2\times n 个点各在一条路径中，定义其权值为 (-1)^{\sigma(p)}，其中 \sigma(p) 是 a_i 与 b_j 匹配的排列的逆序对数。

设矩阵 M，其中 M_{i,j} 为 a_i\to b_j 路径数量，则 M 的行列式等于所有路径组的权值和。

本题问的无非是第一排的点到最后一排点的路径组权值和，所以我们只需要求出路径数量后套用 LGV 引理的结论即可。

路径数量只需要 n_1 次 BFS 就都可以求出，当然也可以直接递推。

这种做法不需要脑子，考场上 2 分钟就能想出来，而且常数显著小于思想类似的矩阵乘法。