PA 2022 Drzewa rozpinające / AGC060F

写一遍 dyh 的做法 /kk。

PA 2022 Drzewa rozpinające

根据 Matrix-tree 定理，我们要计算 \((n-1)\times (n-1)\) 的矩阵的 \(\det\). 设 \(G_{i,j} = \gcd(a_i,a_j),D_{i,i}=\sum_j G_{i,j}\)，要计算 \(\det(D-G)\).

由于 \(\gcd(a_i,a_j)=\sum_{d|a_i,d|a_j}\varphi(d)\)，设两个 \((n-1)\times m\) 的矩阵 \(U,V\)，\(U_{i,d}=\varphi(d)[d|a_i],V_{i,d}=[d|a_i]\)，则有 \(G=UV^T\). （\(V^T\) 是转置矩阵）

下面考虑使用 Matrix determinant lemma 化简式子。

\(\det(D-G) = \det(D-UV^T) = \det(I_m-V^TD^{-1}U)\det(D)\).

\(D\) 是对角矩阵，\(\det\) 好算。于是问题转化为计算 \(\det(I_m-V^TD^{-1}U)\).

设 \(Q=I_m-V^TD^{-1}U\)，只有 \(lcm(i,j)\le m\) 的地方可能有值，对这个稀疏矩阵高斯消元，跑的比较快。

AGC 060 F

设 \(S\) 为总点数，如果直接高斯消元是 \(S^3\) 的。

考虑设计两个 \((S-1)\times m\) 的矩阵 \(U,V\) 使得 \(G=UV^T\)，并且我们希望 \(m\) 能够比较小，这样变形之后可以直接使用 \(O(m^3)\) 的高斯消元。

用点减边就能构造这个信息。