2024.8 #6

T1. [AGC060F] Spanning Trees of Interval Graph

我们令 \(S = \sum C_{i,j}\)。

我们设两个矩阵 \(B_{i,j} = [[L_i,R_i] \cap [L_j,R_j]]\) 以及 \(A_{i,i} = \sum B_{i,j}\)。

那么根据矩阵树定理，我们知道生成树的数量就是 \(\det(A - B)\)。然而直接高斯消元复杂度是 \(O(S^3)\) 的，难以接受。我们需要考虑如何优化 \(A\)。

考虑矩阵行列式引理，我们需要构造出两个 \((S - 1) \times m\) 的矩阵 \(A,B\)，使得 \(G = A \times B^T\)，那么根据矩阵行列式引理：\(\det(D-G) = \det(I - B^TD^{-1}A)\det(D)\)，其中 \(I\) 为单位矩阵。接下来的问题就变成了如何构造大小为 \((S - 1) \times m\) 的矩阵 \(A,B\)。

为了求出 \(A,B\) 后方便计算答案，我们令 \(m = 2 \times n - 1\)。

那么此时我们考虑用两个点来表示两个区间是否有交，不难发现其实就是相交的点数减相交的边数是否为 \(1\)。那么 \(F,G\) 的构造如下：

• \(F_{i,2 \times j - 1} = G_{i,2 \times j - 1} = [j \in [L_i,R_i]]\)

• \(F_{i,2 \times j} = -1 \times [[j,j + 1] \in [L_i,R_i]]\)

• \(G_{i,2 \times j} = [[j,j + 1] \in [L_i,R_i]]\)

那么我们就可以直接利用高斯消元 \(\mathrm O(m^3)\) 求出行列式的值。