PA 2022 Drzewa rozpinające
Rainbow_qwq
·
·
题解
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 化简式子。
$D$ 是对角矩阵，$\det$ 好算。于是问题转化为计算 $\det(I_m-V^TD^{-1}U)$.
设 $Q=I_m-V^TD^{-1}U$，只有 $\operatorname{lcm}(i,j)\le m$ 的地方可能有值，对这个稀疏矩阵高斯消元，跑的比较快。