模板

矩阵运算

定义

det⁡(A)=∑σ∈Snsgn⁡(σ)∏i=1nai,σ(i)\det(A)=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}

拉普拉斯展开

det⁡(A)=∑j=1n(−1)i+jaijMij\det(A)=\sum_{j=1}^n (-1)^{i+j}a_{ij}M_{ij}，MijM_{ij} 为去除 ii 行 jj 列的子式。

三角行列式

若 AA 为上三角或下三角矩阵，则 det⁡(A)=∏i=1naii\det(A)=\prod_{i=1}^n a_{ii}。

简单说一下，仅恒等排列 σ(i)=i\sigma(i)=i 的项非零（其余项必含下三角含有 00 的元素，因为如果一项 << 对应的 ii，一定有一项 >>）。

常见性质

常见性质
    1. 行列式转置后值不变。
    1. 交换两行（列），行列式变号；若两行（列）相同，行列式为 0。
    1. 一行（列）的公因子可提到外面。
    1. 若两行（列）成比例，行列式为 00。
    1. 若一行（列）是两组数之和，可拆成两个行列式相加。
    1. 将一行（列）的倍数加到另一行（列），行列式不变。

计算方法

由这个：

把行列式的某一行(列)的各元素同乘同一个数然后加到另一行(列)对应的元素上去，行列式不变。

我们可以把行列式消成倒三角矩阵。

矩阵树定理

一个图，AA 为图的邻接矩阵，表示两点之间的边的数目，Di,iD_{i,i} 为 ii 的度数。

然后矩阵 L=D−AL=D-A。

然后去掉第 kk 行与第 kk 列(kk 任意)，LL 的值即为生成树的个数。

如果带有边权

我们发现带有重边的情况矩阵树定理可以解决，然后变的个数会乘进答案里面，所以我们直接把边权设为边的个数。

如果是有向的

从根向外的外向树，A 表示入度。

从外向根的内向树，A 表示出度。

P6178 【模板】Matrix-Tree 定理

P6178 【模板】Matrix-Tree 定理。

直接就是模板了，注意对于有向的，需要交换 nn 节点和 11 节点，因为计算的时候需要减去 11 行 11 列。

例题

就记住板子，然后利用这个可以求树的边权的乘积就好了。

P3317 [SDOI2014] 重建

P3317 [SDOI2014] 重建。

这道题是使用了的边的 pip_i 乘上未使用的边的 1−pi1-p_i，我们不希望所有的边都要乘一边权值，所以我们设定初始权值为 1−pi1-p_i，然后边权为 pi1−pi\frac{p_i}{1-p_i}。

P6624 [省选联考 2020 A 卷] 作业题

P6624 [省选联考 2020 A 卷] 作业题。

∑T(∑e∈Twe)⋅gcd⁡e∈T(we)\sum_{T}\left(\sum_{e\in T}w_e\right)\cdot\gcd_{e\in T}(w_e)

利用 gcd⁡=∑d∣gcd⁡φ(d)\gcd = \sum_{d\mid \gcd}\varphi(d) 得：

=∑T(∑e∈Twe)∑d∣we,∀e∈Tφ(d)=∑dφ(d)∑Td∣we,∀e∈T(∑e∈Twe)=\sum_{T}\left(\sum_{e\in T}w_e\right)\sum_{d\mid w_e,\forall e\in T}\varphi(d) \\=\sum_{d}\varphi(d)\sum_{\substack{T\\ d\mid w_e,\forall e\in T}}\left(\sum_{e\in T}w_e\right)

推完之后，我们只需要枚举 dd，然后极端 dd 倍数的生成树边权和。

然后怎么求 和 呢？

我们可以化和为积，在模 x2x^2 意义下，计算 ∑(1+aix)\sum(1+a_i x)。

加减不变。

乘法：(a+bx)⋅(c+dx)=ac+(ad+bc)x(a+bx)\cdot(c+dx) = ac + (ad+bc)x

除法：a+bxc+dx=ac+bc−adc2 x\displaystyle\frac{a+bx}{c+dx} = \frac{a}{c} + \frac{bc-ad}{c^2}\,x

P5296 [北京省选集训2019] 生成树计数

P5296 [北京省选集训2019] 生成树计数。

这是什么东西！

(w1+w2+⋯+wm)k=k![zk]∏i=1mewiz(w_1+w_2+\cdots +w_m)^k = k![z^k]\prod_{i=1}^m \mathrm{e}^{w_iz}

P4336 [SHOI2016] 黑暗前的幻想乡

P4336 [SHOI2016] 黑暗前的幻想乡。

容斥

设 f(n)f(n) 为用指定的 nn 个公司，且不考虑每个公司都修建一条道路的要求，生成树的方案数。

ans=∑i=1n(−1)n−if(i)ans=\sum\limits_{i=1}^n(-1)^{n-i}f(i)

CF917D Stranger Trees

CF917D Stranger Trees。

由于矩阵树定理求的是乘积，我们就把重要的边标记成一个数就行了，然后 kk 次项就是用了 kk 次。最后选 nn 个这种数，然后高斯消元解方程。

P4455 [CQOI2018] 社交网络

P4455 [CQOI2018] 社交网络。

定时练习的题，但是是模板。