NOI 2021 D1T2 题解

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$ 分钟就能想出来，而且常数显著小于思想类似的矩阵乘法。