自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:46:52，当前版本为作者最后更新于2024-09-12 13:14:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$，只有 $\operatorname{lcm}(i,j)\le m$ 的地方可能有值，对这个稀疏矩阵高斯消元，跑的比较快。