Matrix Determinant Lemma
psoet
·
·
个人记录
对于可逆的 A_{n\times n} 和 u_{n\times m}, v_{n\times m}，我们有：
|A+uv^T|=|A||I_m+v^TA^{-1}u|
证明：注意到
\begin{bmatrix}I_n & 0 \\ v^T & I_m \end{bmatrix}
\begin{bmatrix}I_n+uv^T & u \\ 0 & I_m\end{bmatrix}
\begin{bmatrix}I_n & 0 \\ -v^T & I_m \end{bmatrix}
=
\begin{bmatrix}I_n & u \\ 0 & I_m + v^Tu\end{bmatrix}
所以 |I_n + uv^T| = |I_m + v^Tu|。
对原式，我们有 |A+uv^T|=|A||I_n+A^{-1}uv^T|=|A||I_m+v^TA^{-1}u|。
这个东西可以优化一些行列式的求法，我能找到的例子只有矩阵树定理。
令 A 是度数矩阵，我们希望 uv^T 为邻接矩阵。
关键在于 u,v 的构造。
AGC060F 点为 [1,n] 的子区间，有 c_{l,r} 个。两点连边仅当区间有交。
对于连通块，我们有点减边=1。
所以可以令 m=2n-1 分别表示点和边。对于点的部分，我们有 u_{x,i} = v_{x,i} = [i \in x]；对于边的部分，我们有 u_{x,i} = [i \in x],v_{x,i} = -[i \in x]。
n$ 个点，$i,j$ 之间的边数为 $a_ia_j\sigma_0(\gcd(a_i,a_j))$。$n \leq 4000, a_i \leq 5000
由于 \sigma_0(x) = \sum [i|x]，我们可以令 u_{i,j} = v_{i,j} = a_i[j|a_i]。
注意 (v^Tu)_{i,j} 只和 \operatorname{lcm}(i,j)\leq m 有关，所以得到的 m\times m 的矩阵是稀疏的，可以用稀疏矩阵消元（从编号大的往编号小的消）。