『矩阵树定理，LGV引理，行列式』Day9 略解

前言

我抓不住世间的美好，所以只能装作万事顺遂的模样

第二个链接，做是做不起一点的，只能乞讨别考这些**东西。

A

最小带权生成树计数板题。（其实没这么多戏份）

首先先求出任意一颗最小生成树，如果没有直接输出 \(0\)。

对于生成树上的每一种边权分别出来，每次把当前边权在原图上所有的边取出来，然后在树上把树上为这个边权的边删掉，假设树上有 \(k\) 条，那么就会分成 \(k+1\) 个连通块，取出来的边如果两个端点同属一个连通块那么显然没用，如果不属同一个连通块，那就把这两个连通块建一条边。然后把连通块当作点跑一边矩阵树，求得当前生成树计数。

最后根据乘法原理，把每种边权对应的生成树数量乘起来即可。

\(\texttt{Code}\)

C

先用莫比乌斯反演把 \(\gcd\) 拆开，这样就变成了枚举一些权值，所有能用的边就是整除这个权值的边，最后求一遍生成树价值之和，再乘上这个权值的欧拉函数即可。

将行列式的项写成 \(w_i\times x+1\)，最后答案是行列式的一次项系数，因为答案实际上是钦定一条边之后的生成树个数 \(\times\) 这条边的边权之和，那么被乘上一次项系数的边就是被钦定的边。此时可以把高于一次的项忽略掉，复杂度 \(\mathcal{O}(n^3\times d)\)。（其中 \(d\) 表示可能的因子数目。）

\(\texttt{Code}\)

D

这下是真的板子题了。

对于一个最小生成树 \(\mathcal{P}\)，它被选出来的概率是：\(\prod_{(i,j)\in \mathcal{P}} G_{i,j} \times \prod_{(i,j)\notin \mathcal{P}} (1-G_{i,j})\)

可以考虑稍微变个型：\(\prod_{(i,j)}(1-G_{i,j})\times \prod_{(i,j)\in \mathcal{P}} \frac{G_{i,j}}{1-G_{i,j}}\)。

前面那一坨直接乘在外面，后面那一坨当作边权，然后直接跑带权矩阵树定理即可。

注意一下除以 \(0\) 的情况。

\(\texttt{Code}\)

H

别问我为什么中间会空这么多道题。

最大流其实就是我们在上一篇博客中的 \(\text{LGV}\) 扩展应用可以求的东西，就是两个点之间有多少边不相交的路径，然后将边看作点然后建边，跑 \(\text{LGV}\) 即可得到没边权的图的最大流。

开始摘抄题解：

但是直接这样做存在一些问题：

• 起点集合（即 \(1\) 的所有出边）可能很大。我们新建源点 \(s\) 和 \(k\) 个虚点 \(p_1,....p_k\)，连边 \(s\to p_i,p_i\to t\) 即可，其中 \(t\) 为 \(1\) 的任意出点。于是起点集合的大小被我们减小到了 \(\mathcal{O}(k)\)。
• 如果一个点的入度出度均较大，那么这个点的入边出边之间的边数会很大。注意到这些边都会随机赋一个权，相当于每个出边对应的向量为所有入边对应的向量的随机线性组合。于是对于入边，我们只需要保留线性无关的不超过 \(k\) 组向量即可，这个任务可以交给线性基解决。

时间复杂度 \(\mathcal{O}(m\times k^2)\)。

\(\texttt{Code}\)

后记

感觉这个东西难点主要在行列式的组合意义或者它本身的式子对题目的解题效果。

往往我们需要对题目中要求的东西通过变型，来套到行列式或者矩阵上。

这个过程有大量繁琐的推柿子。

真尽力了，数学水平和数学工具不够，也就这做四道题的破水平了。

希望自己未来可以回看，说不定有更深的理解。数学终究还是太菜了。

周末有空对知识点做个总结，没空就只能向前看了，感觉这个版块似乎也没那么重要（？