statement
给定数列 \(w_1,w_2\cdots w_n,w_i\in [1,m]\) ,考虑一个 \(n\) 个点的图,节点 \(i,j\) 之间的边的个数为 \(\sum\limits_{k=1}^m a_{k,w_i}b_{k,w_j}c_k\),你需要求出这个图的生成树个数。
solution
设度数矩阵为 \(D\),邻接矩阵为 \(G\),由矩阵树定理,我们要计算 \(\det(D-G)\)(需要去掉一行一列,这个不影响啥)。
考虑令矩阵 \(A_{i,k}=a_{k,w_i}c_k\),矩阵 \(B_{i,k}=b_{k,w_i}\) ,那么 \(G=AB^{T}\) 。
引理:Matrix Determinant Lemma
设 \(A\) 为方阵 ,\(u,v\) 为列向量 ,那么 \(\det(A+uv^T)=\det(A)\det(I+v^TA^{-1}u)\) ,证明略。
把这里的 \(u,v\) 换成 \(n\times m\) 的矩阵不影响正确性,综上:
\(\det(D-G)=\det(D-AB^T)=\det(D)\det(I_m-B^TD^{-1}A)\) 。
其中 \(D\) 是对角矩阵行列式好算,后面是一个 \(m\times m\) 的矩阵。
更具体的,我们考虑这个 \(m\times m\) 矩阵的每一个位置是啥:
首先 \(B^TD^{-1}\),因为 \(D\) 是对角矩阵,所以逆矩阵就是把每个位置取逆。
那么\((B^TD^{-1})_{i,j}=b_{i,w_j}D^{-1}_{j,j}\) ,\((B^TD^{-1}A)_{i,j}=\sum_{k=1}^nb_{i,w_k}D^{-1}_{k,k}a_{j,w_k}c_j\) 。
直接计算行列式可以做到 \(O(n+m^3)\) 的复杂度。
很多题中,\(A,B\) 都是布尔矩阵,所以这个矩阵比较稀疏,使用稀疏矩阵消元可以做到更加优秀的复杂度。
标签:det,复杂度,矩阵,生成,一类,计数问题,TD,times,sum From: https://www.cnblogs.com/jesoyizexry/p/18063216